# Distance Degree Regular Graphs and Distance Degree Injective Graphs: An Overview

Authors: Medha Itagi Huilgol
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

The distanced
(
v
,
u
) from a vertex v of G to a vertex u is the length of shortest v to u path. The eccentricity
e
v of v is the distance to a farthest vertex from v. If d
(
v
,
u
)
=
e
(
v
)
,
(
u
≠
v
), we say that u is an eccentric vertex of v. The radius
rad
(
G
) is the minimum eccentricity of the vertices, whereas the diameter
diam
(
G
) is the maximum eccentricity. A vertex v is a central vertex if e
(
v
)
=
r
a
d
(
G
), and a vertex is a peripheral vertex if e
(
v
)
=
d
i
a
m
(
G
). A graph is self-centered if every vertex has the same eccentricity; that is, r
a
d
(
G
)
=
d
i
a
m
(
G
). The distance degree sequence (dds) of a vertex v in a graph G
=
(
V
,
E
) is a list of the number of vertices at distance 1
,
2
,
.
.
.
.
,
e
(
v
) in that order, where e
(
v
) denotes the eccentricity of v in G. Thus, the sequence (
d
i
0
,
d
i
1
,
d
i
2
,
…
,
d
i
j
,
…
) is the distance degree sequence of the vertex v
i in G where d
i
j denotes the number of vertices at distance j from v
i. 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.


---

## Body

## 1. Introduction

The study of sequences in Graph Theory is not new. Asequence 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 sequenceS is said to begraphical if there is a graph which realizesS.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. Theeccentric 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], which primarily deal with the conditions for graphical eccentric sequences. The minimal eccentric sequences were mainly studied by Nandakumar [7]. But, for digraphs, the eccentric sequences were studied quite late. We can find some papers in 2008 due to Gimbert and Lopez [8].Next distance based sequences were thepath degree sequences anddistance degree sequences. These were studied by Randic [9] for the purpose of distinguishing chemical isomers by their graph structure. Path degree sequence of a graph has its application in describing atomic environments and in various classification schemes for molecules.We will now define all the terms that give graph theoretic expressions for the above discussed cases.For all undefined terms we refer to [10].LetG
=
(
V
,
E
) denote a graph with the set of vertices V, whose cardinality is theorder
p and two element subsets of V, known asedges forming E, whose cardinality issize
q. Unless mentioned otherwise, in this article, by a graph we mean an undirected, finite graph without multiple edges and self-loops.The distanced
(
v
,
u
) from a vertex v of G to a vertex u is the length of shortest v to u path. Thedegree of a vertex v is the number of vertices at distance one.The sequence of numbers of vertices having degree0,1
,
2,3
,
… is called thedegree sequence, which is the list of the degrees of vertices of G in nondecreasing order.Theeccentricity
e
(
v
) of v is the distance to a farthest vertex from v.The minimum of the eccentricities is theradius
rad
(
G
) and the maximumdiameter of G
,
diam
⁡
(
G
).A graphG is said to beself-centered if all vertices have the same eccentricity.Ifd
(
v
,
u
)
=
e
(
v
)
,
(
u
≠
v
), we say that u is aneccentric vertexof v.Theeccentric sequence of a connected graph G is a list of the eccentricities of its vertices in nondecreasing order.The distance and path degree sequences of a vertex are generalizations of the degree of a vertex. Thedistance degree sequence (dds) of a vertex v in a graph G is a list of the number of vertices at distance 1,2
,
…
,
e
(
v
) in that order, where e
(
v
) denotes the eccentricity of v in G. Thus, the sequence (
d
i
0
,
d
i
1
,
d
i
2
,
…
,
d
i
j
,
…
) is the distance degree sequence of the vertex v
i in G where d
i
j denotes the number of vertices at distance j from v
i. The p-tuple of distance degree sequences of the vertices of G with entries arranged in lexicographic order is the distance degree sequence (DDS) of G. Similarly, we define thepath degree sequence (pds) of v
i as the sequence (
p
i
0
,
p
i
1
,
p
i
2
,
…
,
p
i
j
,
…
) where p
i
j denotes the number of paths in G of length j having v
i as the initial vertex. The ordered set of all such sequences arranged in lexicographic order is called the path degree sequence (PDS) of G. Clearly, for any graph d
i
j
≤
p
i
j.Thedistance distribution of G is the sequence (
d
1
,
d
2
,
…
,
d
j
,
…
), where d
j is the number of pairs of vertices in G that are at distance j apart.Thestatus
s
(
v
) of a vertex v in G is the sum of the distances from v to all other vertices in G. This concept was introduced by Harary [11]. Thus, using the distance degree sequence of v
i, we have s
(
v
i
)
=
∑
j
=
1
diam
⁡
(
G
)
j
d
i
j.Themedian
M
(
G
) of G is the set of vertices withminimum status. A graph is called aself-median graph if all of its vertices have the same status.The status of a vertex is also called thedistance at that vertex. Themean distance at the vertex v
i, denoted by MD
(
v
i
), is defined as MD
(
v
i
)
=
s
(
v
i
)
/
(
p
-
1
).Themean distance for the graph, denoted by MD
(
G
), is defined as the mean of the distances between all pairs of vertices of G; that is, MD
(
G
)
=
∑
{
u
,
v
}
d
(
u
,
v
)
/
p
2, where u and v are vertices of G. In terms of status, we get MD
(
G
)
=
∑
i
=
1
p
(
MD
(
v
i
)
/
p
).As an illustration consider the graphG as shown in Figure 1.Figure 1DDS
(
G
)
=
(
(
1,1
,
1,2
)
,
(
1,2
,
2
)
,
(
1,3
,
1
)
,
(
1,2
,
1,1
)
2
) and PDS
(
G
)
=
(
(
1,1
,
1,2
,
2
)
,
(
1,2
,
2,2
)
,
(
1,2
,
3,2
,
1
)
2
,
(
1,3
,
3
)
).If we consider the 3-dimensional cubeQ
3 as an example, we will get DDS
(
Q
3
)
=
(
(
1,3
,
3,1
)
8
) and PDS
(
Q
3
)
=
(
(
1,3
,
6,12,12,12
)
6
).In [12], Kennedy and Quintas have examined how the distance degree sequences relate to embedding trees in lattice-graphs and other spaces as well as the consequential relations to physical theories. Chemists have also proposed and discussed other sequences for this purpose. Their objective and hope are to develop a “chemical indicator” which would be useful both for the graph isomorphism problem and to predict various properties of the molecule at hand. In this connection, Randic [9] proposed the structural similarity depending on the graph property as follows.Conjecture 1 (see [9]).
Between pairs of atoms in acyclic structures there is a unique path so that the number of paths of a given length corresponds to the number of neighbors at a given distance.This can be rephrased in graph theoretic terms as follows.Conjecture 2 (see [9]).
For a connected graphG, D
D
S
(
G
)
=
P
D
S
(
G
) if and only if G is a tree.A nonassertive proof was given by Quintas and Slater [13].Hence, this kind of study leads to the problem of finding the smallest order for which there exists a pair of nonisomorphic graphs which are equivalent relative to some set of graphical invariants. So the following conjecture was made in line with the above conjecture by Randic [9] that sought for graph isomorphism by comparing their sequences.Conjecture 3 (see [9]).
Two graphsG
1 and G
2 are isomorphic if and only if P
D
S
(
G
1
)
=
P
D
S
(
G
2
).This conjuncture was also shown to be invalid, by citing infinite class of pairs of nonisomorphic trees having the property that the two members of each pair have the same path degree sequence by Quintas and Slater [13]. To extend this notion to nontree graphs, the same examples were considered to construct pairs of nonisomorphic graphs having a variety of properties and invalidate the conjecture.As noted above, a tree is not, in general, characterized by its path (or distance) degree sequence. The least order for which there exists a pair of nonisomorphic trees with the same path degree sequence has been shown to be more than14 for acyclic alkanes, that is, trees with no vertex of degree more than 4 and less than or equal to 18 for trees without vertex degree restrictions.On similar lines one can search for pairs of nonisomorphic graphs having the same distance degree sequence. Slater [14] constructed a pair of nonisomorphic 18 vertex trees having the same distance degree sequence as shown in Figure 2. He had subsequently conjectured that no such smaller order pair exists. Later, Gargano and Quintas [15] considered the problem with respect to the number of independent cycles in a graph having the same distance degree sequence. We can recall that β
=
q
-
p
+
k, where β is the number of independent cycles, k is the number of components in the graph, and p
,
q are the order and size, respectively. For β
=
0, Slater’s constructions hold good. For β
=
1, Gargano and Quintas [15] constructed two pairs of graphs on 14 vertices. For β
=
2, the smallest order pair of nonisomorphic graphs with the same distance degree sequence is given as in Figure 3.Figure 2
A pair of nonisomorphic trees with the same path degree sequence.Figure 3
Smallest order graphs with the same distance degree sequence.And this is the only such pair as noted by Quintas and Slater in [13]. This class of graphs was generalized by Gargano and Quintas [15] for β
≥
2 as follows.Theorem 4 (see [15]).
Ifβ
≥
2, then there exists a pair of nonisomorphic connected graphs having the same distance degree sequence and β independent cycles. The smallest order p for such a pair is given by p
=
⌈
(
3
+
33
+
8
β
)
/
2
⌉, where ⌈
s
⌉ denotes the least integer greater than or equal to s.Two problems were asked in the same paper.Problem 5 (see [15]).
What is the smallest orderp for which there exists a pair of nonisomorphic connected graphs having the same distance degree sequence and β
=
0,1 independent cycles?Problem 6 (see [15]).
What is the smallest orderp for which there exists a pair of nonisomorphic connected graphs having the same distance degree sequence and β
≥
0 (β
≠
2, 3, 4, 5 and 7) independent cycles and such that the graphs have no vertex with degree greater than four?With reference to Problem6, consider the following.Ifβ
=
0, then p is at least 15 (see Slater [14]; p.17).
Ifβ
=
1, Gargano and Quintas [15] conjectured p
=
14.
Ifβ
=
2, the solution is p
=
5 (see Figure 3).For several values ofβ
≥
3, the solution is the same as that for Problem 5. Specifically for β
=
3,4
,
5 and 7 each of the graphs constructed in the proof of the theorem in [15] has no vertex of degree greater than four. Thus the open cases are β
=
0,1
,
6 and β
≥
8.If one asks for the smallest order for which the distance degree sequence fails to distinguish betweenk-regular graphs, there exists the following result due to Quintas and Slater [13].Proposition 7 (see [13]).
LetR
(
k
) denote the smallest order for which there exist at least two nonisomorphic connected k-regular graphs on R
(
k
) vertices such that each has the same distance degree sequence. Then R
(
k
)
=
k
+
3, if k
=
3,4
,
5
,
… and R
(
k
) does not exist if k
=
0,1
,
2.As noted above, there does not exist a pair of nonisomorphic graphs with the same path degree sequence on less than12 vertices. It also follows from the above result that the least order for which such a k-regular pair of graphs can exist is at least k
+
3 for k
≥
3 and that none exist if k
=
0,1
,
2. Thus the investigation to produce at least one pair of nonisomorphic k-regular graphs having the same path degree sequence has resulted in an open problem.Problem 8 (see [13]).
Fork
≥
3, does there exist a pair of nonisomorphic connected k-regular graphs having the same path degree sequence? If the answer is yes, what is the smallest order R
(
k
) realizable by such a pair?In fact, a paper by Slater [14] discusses the counterexamples to Randic’s conjectures on distance degree sequences on trees.In [16] Bussemaker et al. have investigated all connected cubic graphs on p
≤
14 vertices and for each such graph the following properties were determined and tabulated:(i)
its description by means of its edges and forp
≤
12, by a drawing;
(ii)
the coefficients of its characteristic polynomial;
(iii)
the eigenvalues of its(
0,1
)-adjacency matrix;
(iv)
the number of its cycles of length3,4
,
…
,
p;
(v)
its diameter, connectivity, and planarity;
(vi)
the order of its automorphism group.From their table the girth, the circumference, and the chromatic number are easily determined. The graphs were classified according to their order and within each such class the graphs were ordered lexicographically according to their eigenvalues, which for each graph were listed in nonincreasing order. In addition, a number of observations concerning the spectral properties of these graphs were made. The study was motivated by the importance of cubic graphs and by the search for cospectral cubic graphs. The cubic graph generation is looked into by Brinkmann [17]. In [18] Halberstam and Quintas have extended the results of Bussemaker et al. [16] mainly considering the sequences associated with the graphs. In this report they have determined the following information for each cubic graph on less than or equal to 14 vertices:(i)
its distance degree sequence;
(ii)
its distance distribution;
(iii)
the mean distance at each vertex;
(iv)
the mean distance for the graph;
(v)
its path degree sequence;
(vi)
the number of paths of specified length;
(vii)
the total number of paths for the graph.For each graph a number of other parameters can be determined from these tables. The radius, the diameter, and the eccentricity of every vertex can be read directly by noting the length of the appropriate distance degree sequence. By inspection one can determine the order of the center and of the median of the graph. In addition, the computation of other parameters is facilitated by making use of the given data.


## 2. Distance Degree Regular (DDR) Graphs

Now we have the stage set for the discussion on the highly regular class of graphs involving the distance degree sequences, namely, thedistance degree regular graphs. The concept ofdistance degree regular (DDR) graphs was introduced by Bloom et al. [19], as the graphs for which all vertices have the samedistance degree sequence; that is, for all vertices v of a graph G, the distance degree sequence is (
d
i
0
,
d
i
1
,
d
i
2
,
…
,
d
i
j
,
…
).For example, the three-dimensional cubeQ
3
=
K
2
×
K
2
×
K
2 is a DDR graph having (
1,3
,
3,1
) as the distance degree sequence of each of its vertex. Likewise, cycles, complete graphs are all DDR graphs. Lattice-graphs and infinite order regular trees are examples of infinite order DDR graphs. However, in this paper, we consider finite order graphs only. DDR graphs have peculiar relations to many parameters of graphs. On one extreme complete graphs are DDR and at the other end, there are DDR graphs having identity automorphism group. If a graph has a vertex-transitive automorphism group, then the graph is DDR, but not conversely. And the properties of DDR graphs being self-centered and self-median find applications even in operations research. Thus the study of DDR graphs is interesting.In [19], Bloom et al. have discussed many properties of DDR graphs. It is clear that the set of DDR graphs of degree ≤2 consists of the following types: (i) a collection of k isolated vertices, (ii) a collection of k disjoint edges; and (iii) k copies of n-cycles. Hence, the next result is a fundamental one.Proposition 9 (see [19]).
Each regular graph of diameter ≤2 is DDR and the complement of each regular graph of diameter ≥3 is DDR.This result ensures that “every regular graph with diameter at most two is DDR.” We know that every DDR graph is regular, but the distribution of DDR graphs in regular graphs is not clear. So, the following question is relevant.Problem 10 (see [19]).
What proportion ofk-regular graphs are DDR?Following constructions help in getting DDR graphs of arbitrarily chosen diameter and degree. For these methods we require the following terms.Definition 11 (see [19]).
LetG denote a vertex-labeled graph with vertex set V
=
{
1,2
,
…
,
p
}. For any permutation α of V the k-cycle-α-permutation graph of G, denoted by k
C
P
α
(
G
), consists k copies of G joined by the additional edges {
(
i
,
j
)
,
(
α
(
i
)
,
j
+
1
)
}, where (
i
,
j
) is the ith vertex of the jth copy of G and j
+
1
=
1 when j
=
k.Note that the special case2
C
P
α
(
G
) is the α-permutation graph of G
,
P
α
(
G
), introduced by Chartrand and Harary [20], if and only if α is a permutation of order less than or equal to 2. Furthermore, k
C
P
i
d
(
G
) is the cartesian product C
k
×
G of the k-cycle C
k and the graph G. Thus, if G is a n-cycle, it follows that k
C
P
i
d
(
C
n
)
=
n
C
P
i
d
(
C
k
).So the next result gives a family of DDR graphs.Proposition 12 (see [19]).
IfG is any DDR graph of diameter m and degree D
1, then (i) P
i
d
(
G
) is a DDR graph of diameter m
+
1 and degree D
1
+
1 and (ii), for k
≥
3, k
C
P
i
d
(
G
)
=
C
k
×
G is a DDR graph of diameter m
+
⌊
k
/
2
⌋ and degree D
1
+
2.This result can be extended toN iterated cartesian products as shown by the following corollary.Corollary 13 (see [19]).
P
i
d
N
(
G
)
=
K
2
N
×
G has diameter m
+
N and degree D
1
+
N and C
k
N
×
G
≡
C
k
N
-
1
×
G has diameter m
+
N
⌊
k
/
2
⌋ and degree D
1
+
2
N, where P
i
d
N
(
G
)
=
P
i
d
(
P
i
d
N
-
1
(
G
)
)
=
K
2
N
×
G, as P
i
d
(
G
)
=
K
2
N
×
G, that is, the N iterated cartesian products.The existence of a DDR graph having diameterm is shown as follows.Proposition 14 (see [19]).
There exist DDR graphs having diameterm and degree D
1 for all positive integers m and D
1, except for m
>
D
1
=
1.Observe that the only connected1-regular graph is K
2.But, characterizing DDR graphs of higher diameter is challenging. In [19] the following problem was cited.Problem 15 (see [19]).
Characterize DDR graphs having diameter ≥3.Since then there is no answer to this question. A step forward was taken by Huilgol et al. [21], where they have characterized DDR graphs of diameter three with extremal degree regularity. They have shown that there are exactly 7 DDR graphs of diameter three of extreme regularity. The following result gives a clear picture about diameter three DDR graphs.Theorem 16 (see [21]).
LetG be a DDR graph of diameter three of regularity d
1. Then(i)
d
1
=
p
-
4, if and only if G
=
C
6;
(ii)
d
1
=
p
-
5, if and only if G
=
C
7; or G
=
Q
3
=
K
2
×
K
2
×
K
2;
(iii)
d
1
=
p
-
6, if and only if G is one of the graphs given in Figure 4;
(iv)
d
1
=
2, if and only if G
=
C
6 or G
=
C
7.Figure 4The proof of the above theorem is primarily based on the following two results.Proposition 17 (see [3]).
Every connected self-centered graph of orderp satisfies the inequality Δ
≤
p
-
2
r
+
2, where Δ
=
Δ
(
G
) and r
=
rad
(
G
) denote, respectively, the maximum degree and the radius of the graph G.Proposition 18 (see [10]).
In a connected graphG of order p and radius r, for any two arbitrarily chosen vertices u and v, the following inequality holds: deg
⁡
(
u
)
+
deg
⁡
(
v
)
≤
p
-
2
r
+
4.As the diameter three DDR graphs are considered, which are self-centered graphs, satisfying the inequality,2
≤
Δ
(
G
)
≤
p
-
4. In the above theorem, the DDR graphs of regularity 2 are characterized at one extreme and of regularities p
-
4, p
-
5, and p
-
6 at the other extreme of the above mentioned inequality. Using these results, we can find a bound on the order of the graph as p
≤
2
i
-
4, with degree regularity d
1
=
p
-
i. Hence, for the degree regularity d
1
=
p
-
i, i
∈
{
4,5
,
6
}, of a DDR graph of order p, we get p
=
6,8
,
10, respectively. But, in general, the question of characterizing DDR graphs of diameter greater than two still remains open. At least the existence is answered by Huilgol et al. in [21], by proving the following result.Theorem 19 (see [21]).
For any integerk, there exists a DDR graph of diameter three and regularity k.So, the construction of new families of DDR graphs is very interesting. In [22] Huilgol et al. have constructed some more DDR graphs of higher diameter and considered the behavior of DDR graphs under other graph binary operations. In this paper, the authors have given several DDR graphs of arbitrary diameter. Few of them depend on the generalized lexicographic product of graphs.The lexicographic product is defined as follows.Given graphsG and H, the lexicographic product G
[
H
] has the vertex set {
(
g
,
h
)
:
g
∈
V
(
G
)
,
h
∈
V
(
H
)
} and two vertices (
g
,
h
), (
g
′
,
h
′
) are adjacent if and only if either g
g
′ is an edge of G or g
=
g
′ and h
h
′ is an edge of H.Proposition 20 (see [22]).
LetG be a DDR graph and let G
i
,
1
≤
i
≤
p, be undirected graphs such that V
(
G
i
)
=
p, for all i, 1
≤
i
≤
p, and then G
[
G
1
,
G
2
,
G
3
,
…
,
G
p
], the generalized lexicographic product, is a DDR graph if and only if all G
i
,
1
≤
i
≤
p, are regular graphs with the same regularity.This characterizes the generalized lexicographic products. Next result uses the generalized lexicographic product to show the existence of a DDR graph of arbitrary diameter.Proposition 21 (see [23]).
There exists a DDR graph of diameterd
≥
3 of order p
=
(
2
d
+
1
)
n and p
=
2
d
n, where n
=
1,2
,
3
,
….Proposition 22 (see [22]).
There exists a DDR graphG of diameter d such that G
2 is also DDR with diameter d
/
2, if d is even and (
d
+
1
)
/
2, if d is odd.Proposition 23 (see [22]).
IfG is a DDR graph with diameter d and regularity d
1, then the prism of G is also a DDR graph on 2
p number of vertices with diameter d
+
1 and regularity d
1
+
1.In [23], Huilgol et al. have constructed higher order DDR graphs by considering the simplest of the products, namely, the cartesian and normal product. The cartesian product of two graphs G and H, denoted by G
□
H, is a graph with vertex set V
(
G
□
H
)
=
V
(
G
)
×
V
(
H
); that is, the set {
(
g
,
h
)
/
g
∈
V
(
G
)
,
h
∈
V
(
H
)
}. The edge set of G
□
H consists of all pairs [
(
g
1
,
h
1
)
,
(
g
2
,
h
2
)
] of vertices with [
g
1
,
g
2
]
∈
E
(
G
) and h
1
=
h
2 or g
1
=
g
2 and [
h
1
,
h
2
]
∈
E
(
H
).And the normal product of two graphsG and H, denoted by G
⊕
H, is a graph with vertex set V
(
G
⊕
H
)
=
V
(
G
)
×
V
(
H
); that is, the set {
(
g
,
h
)
/
g
∈
V
(
G
)
,
h
∈
V
(
H
)
}, and an edge [
(
g
1
,
h
1
)
,
(
g
2
,
h
2
)
] exists whenever any of the following conditions hold good: (i) [
g
1
,
g
2
]
∈
E
(
G
) and h
1
=
h
2, (ii) g
1
=
g
2 and [
h
1
,
h
2
]
∈
E
(
H
), and (iii) [
g
1
,
g
2
]
∈
E
(
G
) and [
h
1
,
h
2
]
∈
E
(
H
).Theorem 24 (see [23]).
Cartesian product of two graphsG
1 and G
2 is a DDR graph if and only if both G
1 and G
2 are DDR graphs.Lemma 25 (see [23]).
LetS
=
{
G
i
/
i
≥
2
}. If there exists k such that G
k is self-centered and diam
⁡
(
G
k
)
≥
diam
⁡
(
G
i
) for all i
≥
2 then normal product of all the graphs in S is a self-centered graph with diameter equal to diam
⁡
(
G
k
).The next result characterizes the normal product of two DDR graphs.Theorem 26 (see [23]).
Normal productG
1
⊕
G
2 of two graphs G
1 and G
2 is DDR if and only if both G
1 and G
2 are DDR graphs.


## 3. Relationship with Other Properties

As mentioned earlier, the relation of DDR graphs with other graph properties is relatively an unexplored area. In this section we try to relate DDR graphs with some symmetry properties.LetG denote a connected graph with automorphism group Aut
(
G
). Then, G isdistance-transitive, if for each quartet of vertices x, y, u and v in G such that d
(
x
,
y
)
=
d
(
u
,
v
), there is some γ in Aut
(
G
) satisfying γ
(
x
)
=
u and γ
(
y
)
=
v.G issymmetric (1-transitive), if for each quartet of vertices x, y, u, and v in G such that x is adjacent to y and u is adjacent to v, there is some γ in Aut
(
G
) satisfying γ
(
x
)
=
u and γ
(
y
)
=
v.G isvertex-transitive, if, for each pair of vertices x and y in G, there is some γ in Aut
(
G
) satisfying γ
(
x
)
=
u.G isedge-transitive, if for each pair of edges {
x
,
y
} and {
u
,
v
} in G, there is some γ in Aut
(
G
) satisfying γ
{
x
,
y
}
≡
{
γ
(
x
)
,
γ
(
y
)
}
=
{
u
,
v
}.G isdistance-regularwith diameter m, if it is ak-regular connected graph with the following property.There are natural numbersb
0
=
k
,
b
1
,
…
,
b
m
-
1, c
1
=
1
,
c
2
,
…
,
c
m such that for each pair of vertices x and y in G satisfying d
(
x
,
y
)
=
j, it follows that(i)
the number of vertices at distancej
-
1 from y and adjacent to x is c
j
(
1
≤
j
≤
m
);
(ii)
the number of vertices at distancej
+
1 from y and adjacent to x is b
j
(
0
≤
j
≤
m
-
1
).In [24] Biggs has listed the results to show that a symmetric graph is both vertex-transitive and edge-transitive and that a distance-transitive graph is edge-transitive, symmetric, and distance regular. Based on these two results, Bloom et al. [19] proved the following.Proposition 27 (see [19]).
A graph that is vertex-transitive or distance-regular must be DDR.In the next result Bloom et al. [19] have shown that distance degree regularity is weaker than other symmetry conditions and it is also indicated that other well-studied symmetry conditions do not imply DDR.Proposition 28 (see [19]).
Distance degree regularity does not imply edge-transitivity, vertex-transitivity, nor distance-regularity. Also, an edge-transitive graph is not necessarily DDR (and hence neither vertex-transitive, symmetric, nor distance transitive).Vertex-transitivity does not imply edge-transitivity, symmetry, nor distance-regularity. Using the following Bloom et al. [19] have shown that a DDR graph is vertex-transitive, but not distance-regular.The graph shown in Figure5 is C
5
×
C
3, which is a DDR graph. This graph is not distance-regular, as there are two vertices adjacent to both x and y, whereas only one vertex is adjacent to both x and v, given that d
(
x
,
y
)
=
d
(
x
,
v
)
=
2. Also, since the edge {
u
,
v
} lies on a triangle and {
u
,
z
} does not, and these two edges are not equivalent, it shows that the graph is not edge-transitive. Hence, it is not symmetric.Figure 5Distance-regularity does not imply vertex-transitivity. This is shown by an example, noted by Biggs, in [24, p. 139] and attributed to Adel’son-Velskii [25], of a distance-regular graph, hence DDR, with 26 vertices which is not vertex-transitive and, therefore, is neither symmetric nor distance-transitive.Symmetry implies neither distance-transitivity nor distance-regularity. The former observation is demonstrated by a DDR example due to Frucht et al. [26]. They showed the implication did not hold for the permutation graph P
α
(
8
-
c
y
c
l
e
), where α is the permutation (
2,4
)
(
3,7
)
(
6,8
). This is the symmetric generalized Petersen graph P
(
8,3
). Bloom et al. [19] demonstrated the second implication by the DDR example P
i
d
2
(
6
-
c
y
c
l
e
)
=
K
2
2
×
C
6
=
C
4
×
C
6 as shown in Figure 6. This graph can be shown to be symmetric by viewing it on a torus. But we can show that it is not a distance-regular graph on similar lines as done for the graph of Figure 5, by considering the vertex x with the vertices y and u.Figure 6Bloom et al. [19] have shown that most of the well-studied symmetry conditions imply the DDR property. For example, among the four permutation graphs of the 5-cycle, only the most symmetric pair, that is, the P
i
d
(
5
-
c
y
c
l
e
) and the Petersen graph, are DDR. So, they posed the following question, to check the effect of symmetry on permutation graphs.Problem 29 (see [19]).
Whichk-cycle-α-permutation graphs of a given graph are DDR?It is interesting to know that although most symmetry conditions suffice to make a graph DDR, there are DDR examples among the least symmetric graphs. One such class is DDR graphs having identity automorphism group. Ifk
<
3, the only k-regular graph having identity automorphism group is the singleton graph K
1, which is trivially DDR. For k
≥
3, there exist k-regular graphs having identity automorphism group. For these the least order realizable has been determined by [27–30]. Bloom et al. [19] got the least ordered DDR graphs of identity graphs as the complements of the graphs given in [30]. Hence, they proved the following result.Proposition 30 (see [19]).
IfV
(
k
) is the least order realizable by a k-regular DDR graph having identity automorphism group, then V
(
5
)
=
10, V
(
6
)
=
11, and for k
≥
7, V
(
k
)
=
k
+
4, if k is even and V
(
k
)
=
k
+
5, if k is odd.For graphs with regularities 3 and 4 the situation is not clear. Although a least-order3-regular identity graph has 12 vertices, none of the five graphs (see [30]) satisfying this condition is DDR. Thus, V
(
3
)
≥
14. It has also been shown by Haigh (in a private communication to Bloom et al. [19]) that there are no DDR graphs among the 103 cubic identity graphs on 14 vertices which are contained in the complete tabulation of cubic graphs on graphs up to 14 vertices given in [16]. Thus, V
(
3
)
≥
16. But the existence of a order 10 DDR identity graph is shown by Bloom et al. [19]. Also, they posed the following problem.Problem 31 (see [19]).
Ifk
=
3 or 4, do there exist any k-regular DDR graphs having identity automorphism group? If the answer is yes, what is the least order realizable by such graphs?Next we will consider the relation of DDR graphs with a binary relation defined on the graph, namely, the eccentric digraph. Theeccentric digraph of a graph ordigraph is a distance based mapping, defined on a relation induced by distances in a graph or digraph, that is also represented by a graph. Many distance based relations can be found in literature in the study of antipodal graphs [31], antipodal digraphs [31], eccentric graphs [32, 33], and so forth. Theeccentric digraph
ED
(
G
) of a graph (or digraph) G is the digraph that has the same vertex as G and an arc from u to v exists in ED
(
G
) if and only if v is an eccentric vertex of u in G. Eccentric digraphs were defined by Buckley in [34]. In [22], Huilgol et al. have considered the relations between the distance degree regular (DDR) graphs and eccentric digraphs. The DDR graphs being self-centered yield symmetric eccentric digraphs. The study of eccentric digraphs involves the behavior of sequences of iterated eccentric digraphs and they are studied by Gimbert et al. [35]. Given a positive integer k
≥
2, the kth iterated eccentric digraph of G is written as ED
k
(
G
)
=
ED
(
ED
k
-
1
(
G
)
) where ED
0
(
G
)
=
G and ED
1
(
G
)
=
ED
(
G
). For every digraph G there exist smallest integers s
>
0 and t
≥
0 such that ED
t
(
G
)
=
ED
s
+
t
(
G
). In case of labeled graphs s is called theperiod of G and t thetailof G whereas for unlabeled graphs these quantities are referred to asiso-period, denoted by s
′
(
G
) andiso-tail, t
′
(
G
), respectively.In [22] Huilgol et al. have showed that the unique eccentric vertex DDR graphs have all their iterated eccentric digraphs as DDR graphs. In the same paper many results are proved showing the relation between DDR graphs and eccentric digraphs.Proposition 32 (see [22]).
There exists a DDR graphG such that E
D
(
G
)
≅
G.Proposition 33 (see [22]).
There exists a DDR graphG such that E
D
(
G
) is a disconnected graph each of whose components is complete bipartite graph.Proposition 34 (see [22]).
For a unique eccentric vertex DDR graph, ifp
>
4 then tail = 1, period = 2, and if p
=
4, tail = 0, period = 2.Proposition 35 (see [22]).
For a given diameterd
(
≥
3
), there exist 2
d
-
6 DDR graphs with tail = 1 and period = 1.Remark 36.
The unique eccentric vertex DDR graphs have all their iterated eccentric digraphs as DDR graphs.For nonunique eccentric vertex DDR graphs the problem remains still open.Problem 37 (see [22]).
When do nonunique eccentric vertex DDR graphs have all their iterated digraphs as DDR graphs?


## 4. Distance Degree Injective (DDI) Graphs

In contrast to distance degree regular (DDR) graphs the Distance Degree Injective (DDI) graphs are the graphs with no two vertices ofG having the same distance degree sequence (dds). These were also defined by Bloom et al. [36]. So these graphs are highly irregular, compared to the DDR graphs. But, the other extreme of the DDR graphs as we noted above, to have identity automorphism group, becomes an inherent property of DDI graphs, which is evident by the next result.Theorem 38 (see [36]).
IfG is a DDI graph, then G has an identity automorphism group, but not conversely.The converse is obvious as there are DDR graphs with identity automorphism group.As DDR graphs, the characterizations elude DDI graphs. But there are many existential results and examples of DDI graphs.Theorem 39 (see [36]).
A smallest order nontrivial DDI graph has order 7 and there exist DDI graphs having orderp for all p
≥
7.The smallest order nontrivial identity graph has 6 vertices and there are exactly eight identity graphs on 6 vertices and these are not DDI. So the least order is 7. Actually, the identity tree as shown in Figure7 is the smallest DDI graph.Figure 7The following result shows the existence of a DDI graph of arbitrary diameter.Theorem 40 (see [36]).
A smallest diameter nontrivial DDI graph has diameter3 and there exist DDI graphs having diameter m for all m
≥
3.The graphs shown in Figure8 are DDI and have diameter 3 and 4, respectively. The graph of Figure 7 is a DDI graph with diameter 5. For DDI graphs of diameter 6,7
,
… we can consider the same graph as shown in Figure 7 and go on adding vertices on the left of the path P
6.Figure 8Theorem 41 (see [36]).
IfG is a connected DDI graph and G
≠
K
1, then the diameter of G is bounded by 3 and sharply bounded by G
-
2.The following theorem is useful in showing that a graph is not DDI.Theorem 42 (see [36]).
IfG contains two vertices v
1, v
2 with the same degree and such that no vertex of G is further than distance 2 from both v
1 and v
2, then G is not DDI.Note that the complement of the diameter three graph shown in Figure8 is the diameter three identity graph shown in Figure 9. We can see that the above theorem is applicable for this graph and hence it is not DDI.Figure 9But the picture is not clear when we wish to have a graph and its complement to be DDI.Problem 43 (see [36]).
Does there exist a graphG
≠
K
1 such that G and its complement are both DDI?So the next question was onk-regular DDI graphs as posed by Bloom et al. [36].Problem 44 (see [36]).
Does there exist a nontrivialk-regular DDI graph?This problem got resolved by the existence of a cubic DDI graph on 24 vertices and having diameter 10 as found in [37]. The general existence problem was resolved by Bollobas in [38] where he showed the following.Theorem 45 (see [38]).
Letk
≥
3 and ϵ
>
0 be fixed. Set k
=
⌊
1
/
2
+
ϵ
log
⁡
⁡
p
/
log
⁡
⁡
(
k
-
1
)
⌋. Then, as p goes to infinity, the probability tends to one that every vertex v
i in a k-regular labeled graph of order p is uniquely determined by the initial segments d
i
0
,
d
i
1
,
d
i
2
,
…
,
d
i
j of its distance degree sequence.Since the distance degree sequence of a graph is independent of a labeling, this result shows that almost allk-regular graphs of order p are DDI provided that p is large enough. The problem that remains unresolved is that of finding minimal DDI regular graphs.In this direction there was one more problem defined by Halberstam and Quintas [37] as follows.Problem 46 (see [37]).
Fork
≥
3 what is the smallest order and/or diameter for which there exists a k-regular DDI graph?Martinez and Quintas [39] found a cubic DDI graph having diameter 8 and order 22, as in Figure 10. They also showed that if in the graph of Figure 10 the edgesab andcd are replaced by the graph shown in Figure 11, one can obtain a cubic DDI graph with 22
+
2
m vertices and diameter 8
+
m. This was further reduced to order 18 and diameter 7 cubic graph by Volf [40] by constructing the graph of Figure 12.Figure 10Figure 11Figure 12From [18, 36, 37, 39, 40], it follows that(i)
if there is a cubic DDI graph having less than 18 vertices, then its order must be 16;
(ii)
if there is a cubic DDI graph having diameter less than 7, then its diameter must be 4, 5, or 6.So all these cases were considered by Huilgol and Rajeshwari [41] and proved the nonexistence of such a cubic DDI graph.Theorem 47 (see [41]).
There does not exist a cubic DDI graph of order 16 with diameters 4, 5, and 6.So the graph of order 18 as in [40] shown in Figure 12 is the smallest order cubic DDI graph.On the other extreme, construction of new DDI graphs from the smaller order/diameter is also interesting and is looked into by Huilgol et al. [23]. In this paper many results are discussed for different products and the behavior of DDI graphs with respect to these products.Theorem 48 (see [23]).
If the cartesian product of two graphsG
1 and G
2 isDDI then both G
1 and G
2 are DDI graphs.But the converse is not true, as the cartesian product of the DDI graph represented by Figure7 and diameter 4 DDI graph of Figure 8 is not a DDI graph.Lemma 49 (see [23]).
LetG
1 and G
2 be two DDI graphs. Let A
=
{
d
d
s
(
u
i
)
/
u
i
∈
V
(
G
1
)
} and B
=
{
d
d
s
(
v
i
)
/
v
i
∈
V
(
G
2
)
}. If A
∩
B
≥
2 then G
1
□
G
2 is not DDI.Theorem 50 (see [23]).
LetG
1 and G
2 be any two graphs. Let u be a vertex in G
1 and let S be a subset of V
(
G
2
) such that no two vertices of S have the same distance degree sequence; then, no two vertices of {
u
}
×
S have the same distance degree sequence in G
1
□
G
2.LetS
1 and S
2 be two subsets of V
(
G
1
). For each pair (
x
,
y
), with x
∈
S
1 and y
∈
S
2 we can see that dds
(
x
)
≠
dds
(
y
), by applying the Theorem 50. Let z
∈
V
(
G
2
) be any vertex in G
2, and then in G
1
□
G
2, the subsets {
(
x
,
z
)
/
x
∈
S
1
} and {
(
y
,
z
)
/
y
∈
S
2
} are such that every pair (
(
x
,
z
)
,
(
y
,
z
)
)
/
x
∈
S
1
,
y
∈
S
2 satisfies dds
(
x
,
z
)
≠
dds
(
y
,
z
).Similar results are proved for normal product of DDI graphs.Proposition 51 (see [23]).
If the normal productG
1
⊕
G
2 of two graphs is DDI then both G
1 and G
2 are DDI.As in the case of cartesian product, the normal product of two DDI graphs need not be DDI and the same example serves the purpose.Lemma 52 (see [23]).
LetG
1 and G
2 be two DDI graphs. Let A
=
{
d
d
s
(
u
i
)
/
u
i
∈
V
(
G
1
)
} and B
=
{
d
d
s
(
v
i
)
/
v
i
∈
V
(
G
2
)
}. If A
∩
B
≥
2 then G
1
⊕
G
2 is not DDI.Proposition 53 (see [23]).
LetG
1 and G
2 be any two graphs. Let u be a vertex in G
1 and let S be a subset of V
(
G
2
) such that no two vertices of S have the same distance degree sequence; then, no two vertices of {
u
}
×
S have the same distance degree sequence in G
1
⊕
G
2.Remark 54.
Let there be two setsS
1 and S
2, subsets of V
(
G
1
) such that every pair (
x
,
y
), with x
∈
S
1 and y
∈
S
2, satisfies dds
(
x
)
≠
dds
(
y
). Let z
∈
V
(
G
2
) be any vertex in G
2, and then in G
1
⊕
G
2, the subsets {
(
x
,
z
)
/
x
∈
S
1
} and {
(
y
,
z
)
/
y
∈
S
2
} are such that every pair (
(
x
,
z
)
,
(
y
,
z
)
)
/
x
∈
S
1
,
y
∈
S
2 satisfies dds
(
x
,
z
)
≠
dds
(
y
,
z
).


## 5. Embeddings

Kennedy and Quintas [12] considered the extremality of f-trees when they are constrained by embedding either in lattice-graphs or in Euclidean spaces. In chemistry, such constraints appear in the form of postulates concerning the minimal energy which can be attained by certain connectivity patterns of atoms in space. This approach offers a framework ensuring a physical theory to remain self-consistent with respect to its embedding space requirements. So given the distance degree sequence of a graph, it is interesting to see whether we can get some information about the embedding properties of the graph. Hence the next natural question will be on embedding a graph in DDR/DDI graph; if not possible, then try to find the forbidden class of subgraphs. In this context two problems were posed by Bloom et al. [36] which are listed below.Problem 55 (see [36]).
Does there exist a pair of nonisomorphic graphs having the same distance degree sequence and such that one of them is nonplanar with a subgraph homeomorphic toK
5 and the other graph is planar?Problem 56 (see [36]).
Does there exist a pair of nonisomorphic graphs having the same path degree sequence and such that only one of the graphs is planar?At the other extreme Huilgol et al. [42] have considered the embedding of DDR and DDI graphs. The following result rules out the forbidden class of subgraphs for DDR graphs by embedding any graph into a DDR graph.Theorem 57 (see [42]).
Any graph can be embedded in a DDR graph.DDR graphs exhibit high regularity in terms of the vertices and their distance distribution. If we relax one vertex to have different distance degree sequence, then we call such a graph an almost distance degree regular graph, or in short, an ADDR graph. Similarly, we define ADDI graphs.Definition 58 (see [42]).
A graphG of order p is said to be almost DDR if p
-
1 vertices have the same distance degree sequence and one vertex with different distance degree sequence.Definition 59 (see [42]).
A graphG of order p is said to be almost DDI if p
-
2 vertices have different distance degree sequences and two vertices with the same distance degree sequence.Embedding in DDI graphs seems not so easy. But Huilgol et al. [42] could embed only cycles, paths in DDI graphs as follows.Theorem 60 (see [42]).
Any path can be embedded in an almost DDI graph.Proposition 61 (see [42]).
Every cycle can be embedded in a DDI graph.So the following problems were posed in [42].Problem 62 (see [42]).
Can any graph be embedded in a DDI graph?Problem 63 (see [42]).
Does there exist ak-regular DDI graph for k
≥
4?One more problem can be posed at this juncture as follows.Problem 64.
Does there exist a self-centered,k-regular DDI graph?We conclude this article with a comment that even though there are numerous examples and results on DDR and DDI graphs available in literature, the characterizations elude. Hence, many open problems in these areas still persist and keep researchers working.



---

*Source: 358792-2014-12-08.xml*