Diameter Two Graphs of Minimum Order with Given Degree Set

Document Type: Original Scientific Paper

Authors

Ferdowsi University of Mashhad

Abstract

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.

Keywords

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.