%0 Journal Article
%T Distance Degree Regular Graphs and Distance Degree Injective Graphs: An Overview
%A Medha Itagi Huilgol
%J Journal of Discrete Mathematics
%D 2014
%I Hindawi Publishing Corporation
%R 10.1155/2014/358792
%X 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],
%U http://www.hindawi.com/journals/jdm/2014/358792/