Diameter Two Graphs of Minimum Order with Given Degree Set

Document Type : Original Scientific Paper


Ferdowsi University of Mashhad


The degree set of a graph is the set of its degrees. Kapoor et al. [Degree sets for graphs, Fund. Math. 95 (1977) 189-194] proved that for every set of positive integers, there exists a graph of diameter at most two and radius one with that degree set. Furthermore, the minimum order of such a graph is determined. A graph is 2-self- centered if its radius and diameter are two. In this paper for a given set of natural numbers greater than one, we determine the minimum order of a 2-self-centered graph with that degree set.


Main Subjects

1. J. Akiyama, K. Ando and D. Avis, Miscellaneous properties of equi-eccentric graphs, Ann. Discrete Math. 20 (1984) 13-23.
2. F. Buckley, The central ratio of a graph, Discrete Math. 38 (1982) 17-21.
3. F. Göbel, H. J. Veldman, Even graphs, J. Graph Theory 10 (1986) 225-239.
4. S. F. Kapoor, A. D. Polimeni, C. E. Wall, Degree sets for graphs, Fund. Math. 95 (1977) 189-194.
5. Z. Stanić, Some notes on minimal self-centered graphs, AKCE J. Graphs. Comb. 7 (2010) 97-102.
6. I. E. Zverovich, On a problem of Lesniak, Polimeni and Vanderjagt. Rend. Mat. Appl. (7)26 (2006) 211-220.