The distance from a vertex of to a vertex is the length of shortest to path. The eccentricity of is the distance to a farthest vertex from . If , we say that is an eccentric vertex of . The radius is the minimum eccentricity of the vertices, whereas the diameter is the maximum eccentricity. A vertex is a central vertex if , and a vertex is a peripheral vertex if . A graph is self-centered if every vertex has the same eccentricity; that is, . The distance degree sequence (dds) of a vertex in a graph is a list of the number of vertices at distance in that order, where denotes the eccentricity of in . Thus, the sequence is the distance degree sequence of the vertex in where denotes the number of vertices at distance from . The concept of distance degree regular (DDR) graphs was introduced by Bloom et al., as the graphs for which all vertices have the same distance degree sequence. By definition, a DDR graph must be a regular graph, but a regular graph may not be DDR. A graph is distance degree injective (DDI) graph if no two vertices have the same distance degree sequence. DDI graphs are highly irregular, in comparison with the DDR graphs. In this paper we present an exhaustive review of the two concepts of DDR and DDI graphs. The paper starts with an insight into all distance related sequences and their applications. All the related open problems are listed. 1. Introduction The study of sequences in Graph Theory is not new. A sequence for a graph acts as an invariant that contains a list of numbers rather than a single number. A sequence can be handled and studied as easily as a single numerical invariant, but a sequence carries more information about the graph it represents. There are many sequences representing a graph in literature, namely, the degree sequence, the eccentric sequence, the distance degree sequence, the status sequence, the path degree sequence, and so forth. A sequence S is said to be graphical if there is a graph which realizes S. Degree sequences of graphs were the first ones to be studied, as the question of realizability of any sequence for a graph was a fundamental one. An existential characterization was given by Erdos and Gallai [1]. Then the constructive characterization was found independently by Havel [2] and later by Hakimi [3] that is now referred to as the Havel and Hakimi algorithm. The eccentric sequences were the next and the first in the class of distance related sequences to be studied for undirected graphs. Some fundamental results in this direction are due to Lesniak-Foster [4], Ostrand [5], Behzad, and Simpson [6],
References
[1]
P. Erdos and T. Gallai, “Graphs with prescribed degrees of vertices,” Matematikai Lapok, vol. 11, pp. 264–274, 1960 (Hungarian).
[2]
V. Havel, “A remark on the existence of finite graphs,” ？asopis Pro Pěstování Matematiky, vol. 80, pp. 477–480, 1955 (Czech).
[3]
S. L. Hakimi, “On realizability of a set of integers as degrees of the vertices of a linear graph. I,” Journal of the Society for Industrial and Applied Mathematics, vol. 10, pp. 496–506, 1962.
[4]
L. M. Lesniak-Foster, “Eccentric sequences in graphs,” Periodica Mathematica Hungarica, vol. 6, no. 4, pp. 287–293, 1975.
[5]
P. A. Ostrand, “Graphs with specified radius and diameter,” Discrete Mathematics, vol. 4, pp. 71–75, 1973.
[6]
M. Behzad and J. E. Simpson, “Eccentric sequences and eccentric sets in graphs,” Discrete Mathematics, vol. 16, no. 3, pp. 187–193, 1976.
[7]
R. Nandakumar, On some eccentric properties of graphs [PhD Thesis], Indian Institute of Technology, New Delhi, India, 1986.
[8]
J. Gimbert and N. Lopez, “Eccentric sequences and eccentricity sets in digraphs,” Ars Combinatoria, vol. 86, pp. 225–238, 2008.
[9]
M. Randic, “Characterizations of atoms, molecules, and classes of molecules based on paths enumerations,” MATCH, vol. 7, pp. 5–64, 1979.
[10]
F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, 1990.
[11]
F. Harary, “Status and contrastatus,” Sociometry, vol. 22, pp. 23–43, 1959.
[12]
J. W. Kennedy and L. V. Quintas, “Extremal -trees and embedding spaces for molecular graphs,” Discrete Applied Mathematics, vol. 5, no. 2, pp. 191–209, 1983.
[13]
L. V. Quintas and P. J. Slater, “Pairs of nonisomorphic graphs having the same path degree sequence,” Match, no. 12, pp. 75–86, 1981.
[14]
P. J. Slater, “Counterexamples to Randi？’s conjecture on distance degree sequences for trees,” Journal of Graph Theory, vol. 6, no. 1, pp. 89–91, 1982.
[15]
M. Gargano and L. V. Quintas, “Smallest order pairs of non-isomorphic graphs having the same distance degree sequence and specified number of cycles,” in Notes from New York Graph Theory Day VI, pp. 13–16, New York Academy of Sciences, 1983.
[16]
F. C. Bussemaker, S. Cobeljic, D. B. Cvetkovic, and J. J. Seidel, “Computer investigation of cube Graphs,” T. H. Report 76-WSK-01, Technological University Eindhoven, Eindhoven, The Netherlands, 1976.
[17]
G. Brinkmann, “Fast generation of cubic graphs,” Journal of Graph Theory, vol. 23, no. 2, pp. 139–149, 1996.
[18]
F. Y. Halberstam and L. V. Quintas, A Note on Tables of Distance and Path Degree Sequences for Cubic Graphs, Mathematics Department, Pace University, New York, NY, USA, 1982.
[19]
G. S. Bloom, L. V. Quintas, and J. W. Kennedy, “Distance degree regular graphs,” in The Theory and Applications of Graphs, 4th International Conference, Western Michigan University, Kalamazoo, MI, May, 1980, pp. 95–108, John Wiley & Sons, New York, NY, USA, 1981.
[20]
G. Chartrand and F. Harary, “Planar permutation graphs,” Annales de l'Institut Henri Poincaré B, vol. 3, pp. 433–438, 1967.
[21]
M. I. Huilgol, H. B. Walikar, and B. D. Acharya, “On diameter three distance degree regular graphs,” Advances and Applications in Discrete Mathematics, vol. 7, no. 1, pp. 39–61, 2011.
[22]
M. I. Huilgol, M. Rajeshwari, and S. Syed Asif Ulla, “Distance degree regular graphs and their eccentric digraphs,” International Journal of Mathematical Sciences and Engineering Applications, vol. 5, no. 6, pp. 405–416, 2011.
[23]
M. I. Huilgol, M. Rajeshwari, and S. S. A. Ulla, “Products of distance degree regular and distance degree injective graphs,” Journal of Discrete Mathematical Sciences & Cryptography, vol. 15, no. 4-5, pp. 303–314, 2012.
[24]
N. L. Biggs, Algebraic Graph Theory, Cambridge Tracts in Mathematics 67, Cambridge University Press, London, UK, 1974.
[25]
G. M. Adel'son-Velskii, “Example of a graph without a transitive automorphism group,” Soviet Mathematics-Doklady, vol. 10, pp. 440–441, 1969.
[26]
R. Frucht, J. E. Graver, and M. E. Watkins, “The groups of the generalized Petersen graphs,” Proceedings of the Cambridge Philosophical Society, vol. 70, pp. 211–218, 1971.
[27]
A. T. Balaban, R. O. Davies, F. Harary, A. Hill, and R. Westwick, “Cubic identity graphs and planar graphs derived from trees,” Journal of the Australian Mathematical Society, vol. 11, pp. 207–215, 1970.
[28]
G. Baron and W. Imrich, “Asymmetrische regul？re Graphen,” Acta Mathematica Academiae Scientiarum Hungaricae, vol. 20, pp. 135–142, 1969.
[29]
A. Gewirtz, A. Hill, and L. V. Quintas, “El numero minimo de puntos para grafos regulares y asimetricos,” Scientia, vol. 138, pp. 103–111, 1969.
[30]
V. A. Kokhov, “All cubic graphs of least order with identity automorphism group,” Programmirovanie, vol. 4, pp. 106–107, 1976.
[31]
G. Johns and K. Sleno, “Antipodal graphs and digraphs,” International Journal of Mathematics and Mathematical Sciences, vol. 16, no. 3, pp. 579–586, 1993.
[32]
J. Akiyama, K. Ando, and D. Avis, “Eccentric graphs,” Discrete Mathematics, vol. 56, no. 1, pp. 1–6, 1985.
[33]
G. Chartrand, W. Gu, M. Schultz, and S. J. Winters, “Eccentric graphs,” Networks, vol. 34, no. 2, pp. 115–121, 1999.
[34]
F. Buckley, “The Eccentric digraph of a graph,” Congressus Numerantium, vol. 149, pp. 65–76, 2001.
[35]
J. Gimbert, M. Miller, F. Ruskey, and J. Ryan, “Iterations of eccentric digraphs,” Bulletin of the Institute of Combinatorics and Its Applications, vol. 45, pp. 41–50, 2005.
[36]
G. S. Bloom, J. W. Kennedy, and L. V. Quintas, “Some problems concerning distance and path degree sequences,” in Graph Theory, vol. 1018 of Lecture Notes in Mathematics, pp. 179–190, Springer, Berlin, Germany, 1983.
[37]
F. Y. Halberstam and L. V. Quintas, “A note on tables of distance and path degree sequences for cubic graphs,” in Proceedings of the Silver Jubilee Conference on Combinatorics, University of Waterloo, Ontario, Canada, June–July 1982.
[38]
B. Bollobas, “Distinguishing vertices of random graphs,” Annals of Discrete Mathematics, vol. 13, pp. 33–50, 1982.
[39]
P. Martinez and L. V. Quintas, “Distance degree injective regular graphs,” in Notes from New York Graph Theory Day VIII, pp. 19–21, New York Academy of Sciences, New York, NY, USA, 1984.
[40]
J. Volf, “A small distance degree injective cubic graphs,” in Notes from New York Graph Theory Day XIII, pp. 31–32, New York Academy of Sciences, 1987.
[41]
M. I. Huilgol and M. Rajeshwari, “Non-Existence of cubic DDI graphs of order 16 with diameter 4, 5, 6,” (Communicated).
[42]
M. I. Huilgol, M. Rajeshwari, and S. Syed Asif Ulla, “Embedding in distance degree regular and distance degree injective graphs,” Malaya Journal of Mathematik, vol. 4, no. 1, pp. 134–141, 2013.
