Selected Topics in the Extremal Graph Theory
Abstract
Extremal problems in graph theory form a very wide research area. We study the following topics: the metric dimension of circulant graphs, the Wiener index of trees of given diameter, and the degree-diameter problem for Cayley graphs. All three topics are connected to the study of distances in graphs. We give a short survey on the topics and present several new results.
- Keywords
- extremal graph theory, metric dimension, Wiener index, diameter, Cayley graph.
- Classification
- 05C35, 05C12
References
Selected Topics in the Extremal Graph Theory
E. Bannai and T. Ito, Regular graphs with excess one, Discrete Mathematics 37 (1981)
147–158.
P. Cameron, Permutation groups, London Mathematical Society Student Texts 45,
Cambridge University Press (1999) 220 p.
E. DeLaVina and B. Waller, Spanning trees with many leaves and average distance,
Electronic Journal of Combinatorics 15 (2008) 1–16.
V. Faber, J. W. Moore and W. Y. C. Chen, Cycle prefix digraphs for symmetric
interconnection networks, Networks 23 (1993) 641–649.
M. Imran, A. Q. Baig, S. A. Bokhary and I. Javaid, On the metric dimension of circulant
graphs, Applied Mathematics Letters 25 (2012) 320–325.
I. Javaid, M. T. Rahim and K. Ali, Families of regular graphs with constant metric
dimension, Utilitas Mathematica 75 (2008), 21–33.
E. Loz and G. Pineda-Villavicencio, New benchmarks for large scale networks with given
maximum degree and diameter, The Computer Journal 53 (2010) 1092–1105.
H. Macbeth, J. Šiagiová, J. Širáň and T. Vetrík, Large Cayley graphs and vertex-transitive
non-Cayley graphs of given degree and diameter, Journal of Graph Theory 64 (2010)
87–98.
M. J. Morgan, S. Mukwembi and H. C. Swart, On the eccentric connectivity index of a
graph, Discrete Mathematics 311 (2011) 1229–1234.
S. Mukwembi and T. Vetrík: Wiener index of trees of given order and diameter at
most 6, Bulletin of the Australian Mathematical Society 89 (2014) 379–396.
J. Plesník, Critical graph of given diameter, Acta Mathematica Universitatis
Comenianae 30 (1975) 71–93.
T. Vetrík, Cayley graphs of given degree and diameters 3, 4 and 5, Discrete
Mathematics 313 (2013) 213–216.
T. Zhou, J. Xu and J. Liu, On diameter and average distance of graphs, Or Transactions 8
(2004) 1–6.
E. Bannai and T. Ito, Regular graphs with excess one, Discrete Mathematics 37 (1981)
147–158.
P. Cameron, Permutation groups, London Mathematical Society Student Texts 45,
Cambridge University Press (1999) 220 p.
E. DeLaVina and B. Waller, Spanning trees with many leaves and average distance,
Electronic Journal of Combinatorics 15 (2008) 1–16.
V. Faber, J. W. Moore and W. Y. C. Chen, Cycle prefix digraphs for symmetric
interconnection networks, Networks 23 (1993) 641–649.
M. Imran, A. Q. Baig, S. A. Bokhary and I. Javaid, On the metric dimension of circulant
graphs, Applied Mathematics Letters 25 (2012) 320–325.
I. Javaid, M. T. Rahim and K. Ali, Families of regular graphs with constant metric
dimension, Utilitas Mathematica 75 (2008), 21–33.
E. Loz and G. Pineda-Villavicencio, New benchmarks for large scale networks with given
maximum degree and diameter, The Computer Journal 53 (2010) 1092–1105.
H. Macbeth, J. Šiagiová, J. Širáň and T. Vetrík, Large Cayley graphs and vertex-transitive
non-Cayley graphs of given degree and diameter, Journal of Graph Theory 64 (2010)
87–98.
M. J. Morgan, S. Mukwembi and H. C. Swart, On the eccentric connectivity index of a
graph, Discrete Mathematics 311 (2011) 1229–1234.
S. Mukwembi and T. Vetrík: Wiener index of trees of given order and diameter at
most 6, Bulletin of the Australian Mathematical Society 89 (2014) 379–396.
J. Plesník, Critical graph of given diameter, Acta Mathematica Universitatis
Comenianae 30 (1975) 71–93.
T. Vetrík, Cayley graphs of given degree and diameters 3, 4 and 5, Discrete
Mathematics 313 (2013) 213–216.
T. Zhou, J. Xu and J. Liu, On diameter and average distance of graphs, Or Transactions 8
(2004) 1–6.