The distanced(v,u)from a vertexvofGto a vertexuis the length of shortestvtoupath. Theeccentricityevofvis the distance to a farthest vertex fromv. Ifd(v,u) = e(v), (u ≠ v), we say thatuis aneccentric vertexofv. Theradiusrad(G)is theminimum eccentricityof the vertices, whereas thediameterdiam(G)is themaximum eccentricity. A vertexvis acentral vertexife(v) = rad(G), and a vertex is aperipheral vertexife(v) = diam(G). A graph isself-centeredif every vertex has the same eccentricity; that is,rad(G) = diam(G). Thedistance degree sequence (dds)of a vertexvin a graphG = (V, E)is a list of the number of vertices at distance1, 2, ... . , e(v)in that order, wheree(v)denotes the eccentricity ofvinG. Thus, the sequence(di0,di1,di2, …, dij,…)is the distance degree sequence of the vertexviinGwheredijdenotes the number of vertices at distancejfromvi. The concept ofdistance degree regular (DDR) graphswas 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 isdistance degree injective (DDI) graphif 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.
展开▼
