# On the Distance Pattern Distinguishing Number of a Graph

Authors: Sona Jose; Germina K. Augustine
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

LetG
=
(
V
,
E
) be a connected simple graph and let M be a nonempty subset of V. The M-distance pattern of a vertex u in G is the set of all distances from u to the vertices in M. If the distance patterns of all vertices in V are distinct, then the set M is a distance pattern distinguishing set of G. A graph G with a distance pattern distinguishing set is called a distance pattern distinguishing graph. Minimum number of vertices in a distance pattern distinguishing set is called distance pattern distinguishing number of a graph. This paper initiates a study on the problem of finding distance pattern distinguishing number of a graph and gives bounds for distance pattern distinguishing number. Further, this paper provides an algorithm to determine whether a graph is a distance pattern distinguishing graph or not and hence to determine the distance pattern distinguishing number of that graph.


---

## Body

## 1. Introduction

One of the basic problems in graph theory is to select a minimum setS of vertices in such a way that each vertex in the graph is uniquely determined by the distances to the chosen vertices. The vertices in that set uniquely determine the positions of the remaining vertices of the graph. Slater [1] defined the code of a vertex v with respect to a k-tuple of vertices S
=
(
v
1
,
v
2
,
…
,
v
k
) as (
d
(
v
,
v
1
)
,
d
(
v
,
v
2
)
,
…
,
d
(
v
,
v
k
)
), where d
(
v
,
v
j
) denotes the distance of the vertex v from the vertex v
j. Thus, entries in the code of a vertex may vary from 0 to diameter of G. If the codes of the vertices are to be distinct, then the subset S is called resolving set of that graph. A resolving set S of minimum cardinality is called a metric basis and |
S
| is called the metric dimension of G.In 2006, Dr. B. D. Acharya introduced a new concept which is distance pattern distinguishing set of a graph. A detailed study of this concept has been done in [2, 3]. A distance pattern distinguishing set identifies the automorphism group of a graph and each vertex in the graph is uniquely identified by its graph properties and its relationship to the vertices of the distance pattern distinguishing set. However, a distance pattern distinguishing set of a graph G (if it exists) need not be unique. Hence, determination of the minimum cardinality of a distance pattern distinguishing set in G is an interesting problem to be investigated. This paper focuses on the problem of determining the minimum cardinality, ϱ
(
G
), of a distance pattern distinguishing set in a graph G and gives an algorithm to determine whether a graph G has a distance pattern distinguishing set and also to determine ϱ
(
G
), if it exists. In this paper we consider finite, simple, and connected graphs.Definition 1.
For an arbitrarily fixed vertexu in G and for any nonnegative integer j, let N
j
[
u
]
=
{
v
∈
V
(
G
)
:
d
(
u
,
v
)
=
j
} and N
j
[
u
]
=
V
(
G
)
-
V
(
C
u
) whenever j exceeds the eccentricity ɛ
(
u
) of u in the component C
u to which u belongs. Thus, if G is connected, then N
j
[
u
]
=
∅ if and only if j
>
ɛ
(
u
). We can generalize this concept as, given an arbitrary nonempty subset M
⊆
V
(
G
) and for each u
∈
V
(
G
), N
j
M
(
u
)
=
{
v
∈
M
:
d
(
u
,
v
)
=
j
}.Definition 2.
LetG be a given connected simple graph, ∅
≠
M
⊆
V
(
G
), and u
∈
V
(
G
). Then, the M-distance pattern of u is the set f
M
(
u
)
=
{
d
(
u
,
v
)
:
v
∈
M
}. Clearly, f
M
(
u
)
=
{
j
:
N
j
M
[
u
]
≠
∅
}. If f
M
:
u
↦
f
M
(
u
) is an injective function, then the set M is said to be a distance pattern distinguishing set of G. A graph G with distance pattern distinguishing set is called a distance pattern distinguishing graph. The number of vertices in a minimum distance pattern distinguishing set is called the distance pattern distinguishing number of G and it is denoted by ϱ
(
G
).
The expressibility of graphs and matrices in terms of each other is well known. Each of these two mathematical models has certain operational advantages. Definition3 brings a matrix, related to the distance patterns of the vertices of a graph G with respect to a subset M of vertices and Lemma 4 characterizes the distance pattern distinguishing set of a graph in terms of (
0,1
)-matrix that is defined as follows.Definition 3.
For an arbitrary nonempty subsetM
⊆
V
(
G
), the p
×
(
d
G
+
1
) matrix D
G
M
=
(
|
N
j
-
1
M
(
v
i
)
|
); i
=
1,2
,
…
,
p; j
=
1,2
,
…
,
(
d
G
+
1
), where d
G that denotes the diameter of G is called the M distance neighborhood pattern matrix of G. Let D
G
*
M be the (
0,1
) matrix build from D
G
M by replacing each nonzero entry by 1.Lemma 4 (see [3]).
In any graphG, a nonempty M
⊆
V
(
G
) is a distance pattern distinguishing set if and only if no two rows of D
G
*
M are identical.Example 5.
Consider the graphG given in Figure 1. Now, M
=
{
a
,
d
,
c
} is a distance pattern distinguishing set of G since
(1)
f
M
(
a
)
=
{
0,1
,
3
}
,
f
M
(
b
)
=
{
1,2
,
3
}
,
f
M
(
c
)
=
{
0,2
,
3
}
,
f
M
(
d
)
=
{
0,1
,
2
}
,
f
M
(
e
)
=
{
1,2
}
.
Also,
(2)
N
0
M
(
a
)
=
{
a
}
,
N
1
M
(
a
)
=
{
d
}
,
N
2
M
(
a
)
=
∅
,
N
3
M
(
a
)
=
{
c
}
,
N
0
M
(
b
)
=
∅
,
N
1
M
(
b
)
=
{
d
}
,
N
2
M
(
b
)
=
{
a
}
,
N
3
M
(
b
)
=
{
c
}
,
N
0
M
(
c
)
=
{
c
}
,
N
1
M
(
c
)
=
∅
,
N
2
M
(
c
)
=
{
d
}
,
N
3
M
(
c
)
=
{
a
}
,
N
0
M
(
d
)
=
{
d
}
,
N
1
M
(
d
)
=
{
a
}
,
N
2
M
(
d
)
=
{
c
}
,
N
3
M
(
d
)
=
∅
,
N
0
M
(
e
)
=
∅
,
N
1
M
(
e
)
=
{
c
,
d
}
,
N
2
M
(
e
)
=
{
a
}
,
N
3
M
(
e
)
=
∅
,
and the M-distance pattern neighborhood matrix is
(3)
D
G
M
=
(
1
1
0
1
0
1
1
1
1
0
1
1
1
1
1
0
0
2
1
0
)
,
D
G
*
M
=
(
1
1
0
1
0
1
1
1
1
0
1
1
1
1
1
0
0
1
1
0
)
.Figure 1


## 2. Distance Pattern Distinguishing Number of a Graph

Theorem 6 (see [3]).
A cycleC
n of order n admits a distance pattern distinguishing set if and only if n
≥
7.Theorem 7 (see [2]).
LetG be any distance pattern distinguishing graph with a distance pattern distinguishing set M. Then, the induced graph G
[
M
] is disconnected.The following theorem provides the distance pattern distinguishing number of some well-known classes of graphs.Theorem 8.
(a) The trivial graph K
1 is the only graph with distance pattern distinguishing number as the order of that graph.
(b) Path is the only graph with distance pattern distinguishing number one.
(c) There exists no graph with distance pattern distinguishing number 2.
(d)  ϱ
(
C
n
)
=
3, for all n
≥
7.Proof.
(a) Assume thatG is isomorphic to K
1. Clearly, K
1 has the distance pattern distinguishing set M
=
{
v
}, where V
(
K
1
)
=
{
v
} and hence, ϱ
(
K
1
)
=
O
(
K
1
).
Converse follows from the fact that ifM
=
V
(
G
), then the distance patterns of diametrically opposite vertices are identical.
(b) It can be easily verified that one of the two pendant vertices of a path forms a distance pattern distinguishing set and hence distance pattern distinguishing number of a path is one. For the converse part, we assume thatG
≇
P
n and that the distance pattern distinguishing set is a vertex u of G. First observe that the degree of u is 1; otherwise, the vertices adjacent to u have the same distance pattern as {
1
}. Since G is not a path, it contains a vertex whose degree is at least three. Let v be such a vertex of G with the least d
(
u
,
v
) and let A
=
{
v
1
,
v
2
,
…
,
v
k
} be the set of all vertices adjacent to v. Then, the distance pattern of each of the vertices in A is any one of {
d
-
1
}, {
d
}, or {
d
+
1
}, where d
=
d
(
u
,
v
). None of the vertices in A may have the distance pattern {
d
}, as it is the distance pattern of the vertex v. Therefore, since |
A
|
≥
3, at least two vertices in A have the same distance pattern, a contradiction.
(c) Let two verticesu and v form a distance pattern distinguishing set of a graph G. Then the distance pattern of u and v is the same and f
M
(
u
)
=
f
M
(
v
)
=
{
0
,
d
(
u
,
v
)
}, which is a contradiction to the concept of distance pattern distinguishing set. Hence, (c) holds.
(d) LetC
n
=
v
1
v
2
⋯
v
n
v
1 be a cycle on n vertices. By Theorem 6, C
n; n
≤
6 is not a distance pattern distinguishing graph. Also from (b) and (c), it follows that distance pattern distinguishing number of a cycle is not equal to one or two. Consider M
=
{
v
1
,
v
2
,
v
4
}. Then, the rows representing the M-distance neighborhood pattern of v
1
,
v
2
,
…
,
v
n (taken in order) in D
G
*
M, are given as follows.
Case
1. n is an even integer and n
≥
7. Consider
(4)
D
G
*
M
=
(
1
1
0
1
0
0
⋯
0
0
0
0
0
0
1
1
1
0
0
0
⋯
0
0
0
0
0
0
0
1
1
0
0
0
⋯
0
0
0
0
0
0
1
0
1
1
0
0
⋯
0
0
0
0
0
0
0
1
0
1
1
0
⋯
0
0
0
0
0
0
0
0
1
0
1
1
⋯
0
0
0
0
0
0
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
0
0
0
0
0
0
⋯
0
1
0
1
1
0
0
0
0
0
0
0
⋯
0
0
1
0
1
1
0
0
0
0
0
0
⋯
0
0
0
1
1
1
0
0
0
0
0
0
⋯
0
0
0
1
1
0
0
0
0
0
0
0
⋯
0
0
1
1
0
1
0
0
0
0
0
0
⋯
0
1
1
0
1
0
0
0
0
0
0
0
⋯
1
1
0
1
0
0
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
0
1
1
0
1
0
⋯
0
0
0
0
0
0
)
.
Case
2. n is an odd integer and n
≥
7. Consider
(5)
D
G
*
M
=
(
1
1
0
1
0
0
⋯
0
0
0
0
0
0
1
1
1
0
0
0
⋯
0
0
0
0
0
0
0
1
1
0
0
0
⋯
0
0
0
0
0
0
1
0
1
1
0
0
⋯
0
0
0
0
0
0
0
1
0
1
1
0
⋯
0
0
0
0
0
0
0
0
1
0
1
1
⋯
0
0
0
0
0
0
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
0
0
0
0
0
0
⋯
0
0
1
0
1
1
0
0
0
0
0
0
⋯
0
0
0
1
0
1
0
0
0
0
0
0
⋯
0
0
0
0
1
1
0
0
0
0
0
0
⋯
0
0
0
1
1
1
0
0
0
0
0
0
⋯
0
0
1
1
0
1
0
0
0
0
0
0
⋯
0
1
1
0
1
0
0
0
0
0
0
0
⋯
1
1
0
1
0
0
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
0
1
1
0
1
0
⋯
0
0
0
0
0
0
)
.
In both of the cases it can be seen that none of the rows are identical and so M
=
{
v
1
,
v
2
,
v
4
} forms a distance pattern distinguishing set of C
n, which yields the desired result.Theorem8 motivates one to raise the following problem of theoretical interest.Problem 1.
Given a natural numberk, other than 2, does there exist a graph G whose distance pattern distinguishing number is k? Is G unique for that k?The following three theorems establish sharp bounds for the distance pattern distinguishing number of a graph.Theorem 9.
LetG be a graph of order n with diameter d and distance pattern distinguishing number ϱ. Then, n
+
1
-
2
d
≤
ϱ
≤
2
d
-
(
d
+
1
).Proof.
LetG be a graph with diameter d and distance pattern distinguishing number ϱ. Then, for all v
∈
V, f
M
:
V
(
G
)
→
2
S
∖
{
∅
} where S
=
{
0,1
,
…
,
d
} is an injective function.
Upper Bound. Let u
∈
M. There is at most 2
d
-
1 choices for f
M
(
u
) and 0
∈
f
M
(
u
). By Theorem 8, there is no distance pattern distinguishing set of cardinality 2 and therefore we exclude all 2-element sets, for which one of the two elements is zero, from the choices. Thus, the upper bound ϱ
≤
2
d
-
(
d
+
1
) holds.
Lower Bound. For the lower bound, since f
M is injective, each vertex in G has distinct distance pattern of cardinality at most ϱ. Hence, G has at most ϱ
+
∑
j
=
1
d
C
j
d vertices. But ∑
j
=
0
d
C
d
j
=
2
d, which implies that ϱ
≥
n
+
1
-
2
d.The inequality given in the lower bound of Theorem9 can be strict. For example, by Theorem 8, the cycle C
7 of an order n
=
7 and diameter d
=
3 has the distance pattern distinguishing number ϱ
(
C
7
)
=
3, but n
+
1
-
2
d
=
0. On the other hand, the path P
2 shows that the lower bound in Theorem 9 can be sharp since P
2 has order n
=
2 and diameter d
=
1, while either end-vertex of P
2 constitutes a distance pattern distinguishing set and so n
+
1
-
2
d
=
1 and ϱ
(
P
2
)
=
1.The upper bound in Theorem9 can be attained for the path P
3 of order n
=
3 and diameter d
=
2 for which the distance pattern distinguishing number ϱ
(
P
3
)
=
1. But the upper bound cannot be sharp for the paths P
n, n
≥
4.It can be seen that every distance pattern distinguishing set of a graph is a resolving set of that graph. But not every resolving set is a distance pattern distinguishing set; the smallest counterexample isK
3. Hence, the distance pattern distinguishing number of a graph may be the same as the metric dimension of that graph. Chartrand et al. obtained a sharp lower bound for the metric dimension of a graph in terms of maximum degree of G [4]. By similar arguments, it can be shown that the same bound holds for distance pattern distinguishing number also. We exclude the proof in this case.Theorem 10.
IfG is a distance pattern distinguishing graph with diameter d and maximum degree Δ, then ϱ
(
G
)
≥
⌜
log
⁡
3
⁡
(
Δ
+
1
)
⌝.The lower bound in Theorem10 can be attained for graphs G
≅
P
n. On the other hand, if G
≅
C
n, then the lower bound given in Theorem 10 cannot be sharp.Remark 11.
The upper boundβ
(
G
)
≤
p
-
d for the metric dimension of a graph in terms of diameter of G given by Chartrand et al. [4] is not valid for distance pattern distinguishing number of that graph. For example, let G be a graph obtained from C
4 by attaching a path of lengthtwo to an arbitrary vertex of C
4. Then, ϱ
(
G
)
=
4, which implies that the inequality does not hold for the distance pattern distinguishing number of G.The result that follows uses the following definitions and notations recalled from [5].Definition 12.
LetT
=
(
V
,
E
) be a tree and let v be a specified vertex in T. Partition the edges of T by the equivalence relation =
v defined as follows: two edges e
=
v
f if and only if there is a path in T including e and f that does not have v as an internal vertex. The subgraphs induced by the edges of the equivalent classes of E are called the bridges of T relative to v. For each vertex v
∈
V of a tree T
=
(
V
,
E
), the legs at v are the bridges which are paths. We use l
v to denote the number of legs at v.Theorem 13.
For a treeT
≇
P
n, ϱ
≥
∑
v
∈
V
:
l
v
>
1
(
l
v
-
1
).Proof.
LetT
≇
P
n be a tree with distance pattern distinguishing set M. Consider any vertex v with l
v
>
1. Then at least l
v
-
1 legs of v contain vertices in M. Otherwise, let l
1 and l
2 be two legs of v whose vertices are not the elements of M. Then the neighbors of v in those legs have the same distance pattern with respect to M, a contradiction. Therefore, for each vertex v
∈
V at least l
v
-
1 are in M. Since T is not a path, the legs corresponding to distinct vertices are disjoint. Therefore, distance pattern distinguishing number is at least the sum stated above.The following lemma gives a class of graphs attaining the lower bound in Theorem13.Definition 14.
An olive treeT
k is a rooted tree that consisted of k branches, and the i
th branch is a path of length i.Lemma 15.
Olive treeT
k with k
≥
3 branches has distance pattern distinguishing number k
-
1.Proof.
SinceT
1
≅
P
2 and T
2
≅
P
4, by Theorem 8, ϱ
(
T
1
)
=
ϱ
(
T
2
)
=
1. Let T
k be an olive tree with branches t
1
,
t
2
,
…
,
t
k, where k
≥
3 and let v be its root vertex. Then, l
v
=
k and for all u
∈
V
∖
{
v
}, l
u
=
1. Let M be a distance pattern distinguishing set in T
k. Then by Theorem 13, M contains vertices from at least k
-
1 branches and ϱ
≥
∑
v
∈
V
:
l
v
>
1
(
l
v
-
1
)
=
k
-
1. Now, we prove the lemma by showing that pendant vertices from the branches, t
1
,
t
2
,
…
,
t
k
-
1, form a distance pattern distinguishing set.
We denote the vertices on thei
th branch of T successively from the vertex adjacent to v to the pendant vertex of the branch as v
i
1
,
v
i
2
,
v
i
3
,
…
,
v
i
i. Let M
=
{
v
11
,
v
22
,
…
,
v
k
-
1
k
-
1
}. Then, the rows corresponding to the vertices in the kth branch together with the row corresponding to v form a submatrix of D
T
*
M as follows:
(6)
(
0
0
0
0
·
0
0
0
1
·
1
1
1
1
1
·
1
1
1
0
0
0
0
·
0
0
1
1
·
1
1
1
1
1
·
1
1
0
0
0
0
0
·
0
1
1
1
·
1
1
1
1
1
·
1
0
0
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
0
0
1
1
·
1
1
1
1
1
·
·
1
1
0
0
0
·
0
0
1
1
1
·
1
1
1
1
1
·
·
1
0
0
0
0
·
0
)
,
where in the first row 1 appears at the (
k
+
2
)
th
,
(
k
+
3
)
th
,
…
,
(
2
k
)
th positions and from the second row onwards the entry 1 at each position is shifted one position to the left. Rows corresponding to the vertices in the (
k
-
1
)
th branch form a submatrix of D
T
*
M as follows:
(7)
(
1
0
0
0
·
0
0
0
1
·
1
1
1
1
·
1
1
0
0
0
1
0
0
·
0
0
1
1
·
1
1
1
1
·
1
0
0
0
0
0
1
0
·
0
1
1
1
·
1
1
1
1
·
0
0
0
0
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
0
0
1
1
·
1
1
1
1
1
·
·
·
1
0
0
0
·
0
)
,
where in the first row 1 appears at the first, (
k
+
1
)
th
,
(
k
+
2
)
th
,
…
,
(
2
k
-
2
)
th positions. From the second row onwards the entry 1 at the first position is shifted one position to the right and the entry 1 at (
k
+
2
)
th
,
(
k
+
3
)
th
,
…
,
(
2
k
-
1
)
th positions is shifted one position to the left. When 3
≤
i
≤
(
k
-
2
), the rows corresponding to the vertices in the i
th branch form a submatrix of D
T
*
M are as follows:
(8)
(
1
0
0
0
·
0
0
0
1
·
1
1
1
0
1
·
1
1
1
0
·
0
0
1
0
0
·
0
0
1
1
·
1
1
0
1
1
·
1
1
0
0
·
0
0
0
1
0
·
0
1
1
1
·
1
0
1
1
1
·
1
0
0
0
·
0
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
0
0
0
1
·
1
1
1
0
1
·
·
·
1
0
0
0
·
0
0
0
0
)
,
where in the first row 1 appears at the first, (
i
+
2
)
th
,
(
i
+
3
)
th
,
…
,
(
2
i
)
th
,
(
2
i
+
2
)
th
,
(
2
i
+
3
)
th
,
…
,
(
i
+
k
)
th positions. From the second row onwards the entry 1 at the first position is shifted one position to the right and the entry 1 at (
i
+
2
)
th
,
(
i
+
3
)
th
,
…
,
(
2
i
)
th
,
(
2
i
+
2
)
th
,
(
2
i
+
3
)
th
,
…
,
(
i
+
k
)
th positions is shifted one position to the left.
Thus, all the rows inD
T
*
M are nonidentical and hence, M is a distance pattern distinguishing set. Hence, an olive tree with k branches has distance pattern distinguishing number k
-
1.Lemma 16.
LetK
n with n
≥
4 be a complete graph with V
(
K
n
)
=
{
v
1
,
v
2
,
…
,
v
n
}. Let G be the graph obtained from K
n by attaching path P
i
:
v
i
1
,
v
i
2
,
…
,
v
i
i to v
i for all i
=
1,2
,
…
,
n. Then, ϱ
(
G
)
=
n
-
1.Proof.
LetK
n be a complete graph with V
(
K
n
)
=
{
v
1
,
v
2
,
…
,
v
n
}. Let G be the graph obtained from K
n by attaching path P
i
:
v
i
v
i
1
v
i
2
⋯
v
i
i to v
i for all i
=
1,2
,
…
,
n. Then, at least n
-
1 paths P
i contain vertices in M. Otherwise, let P
i and P
j be two paths whose vertices are not in M. Then, f
M
(
v
i
)
=
f
M
(
v
j
), a contradiction. Therefore, at least n
-
1 vertices are in M. Choose M
=
{
v
11
,
v
22
,
…
,
v
n
-
1
,
n
-
1
}. Then, the rows corresponding to the vertices in the path P
i; i
=
1,2
,
…
,
n
-
1 in D
G
*
M are of the form
(9)
(
1
0
0
0
·
0
0
0
1
·
1
1
1
0
1
·
1
1
1
0
·
0
0
1
0
0
·
0
0
1
1
·
1
1
0
1
1
·
1
1
0
0
·
0
0
0
1
0
·
0
1
1
1
·
1
0
1
1
1
·
1
0
0
0
·
0
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
0
0
1
1
·
1
1
0
1
·
1
1
1
1
0
·
0
0
0
0
·
0
0
1
1
1
·
1
0
1
1
·
1
1
1
0
0
·
0
0
0
0
·
0
)
,
where in the first row the entry 1 appears at the 1
st
,
(
i
+
3
)
th
,
(
i
+
4
)
th
,
…
,
(
2
i
+
1
)
th
,
(
2
i
+
3
)
th
,
…
,
(
n
+
i
+
1
)
th columns. From the second row onwards the entry 1 in the first position shifts one position to the right and the entry 1 in (
i
+
3
)
th
,
(
i
+
4
)
th
,
…
,
(
2
i
+
1
)
th
,
(
2
i
+
3
)
th
,
…
,
(
n
+
i
+
1
)
th positions shifts one position to the left. The rows corresponding to the vertices of the path P
n in D
G
*
M are of the form
(10)
(
1
0
0
0
·
0
0
0
1
·
1
1
1
0
1
0
0
·
0
0
1
1
·
1
1
0
0
0
1
0
·
0
1
1
1
·
1
0
0
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
0
0
1
1
·
1
1
1
0
·
0
0
0
0
1
1
1
·
1
1
0
0
·
0
0
0
)
,
where in the first row the entry 1 appears at the 1
st
,
(
n
+
3
)
th
,
(
n
+
4
)
th
,
…
,
(
2
n
+
1
)
th columns. From the second row onwards the entry 1 in the first position shifts one position to the right and the entry 1 in (
n
+
3
)
th
,
(
n
+
4
)
th
,
…
,
(
2
n
+
1
)
th positions shifts one position to the left. It is easy to see that the rows in D
G
*
M are nonidentical and therefore, M is a distance pattern distinguishing set.Theorem 17.
Given any positive integerk
≠
2, there exists a graph G with ϱ
(
G
)
=
k. Furthermore, G is not unique except for k
=
1.Proof.
By Theorem8, P
n is the only graph with ϱ
=
1. From Lemmas 15 and 16 we have that, given any positive integer k
≥
3, there exists more than one class of graphs with ϱ
=
k.


## 3. Algorithm

LetD
=
(
d
i
j
) denote the distance matrix of a graph G and let ∅
≠
M
⊆
V with |
M
|
=
k. Let D
′ be an n
×
k
;
1
≤
k
≤
n submatrix of D whose columns correspond to the vertices in M. Then each row of D
′ (considered as a set) gives the M distance patterns of the corresponding vertices in G. Thus, we can check whether M is a distance pattern distinguishing set or not. We design the following algorithm to determine whether a graph is a distance pattern distinguishing graph or not and to determine the distance pattern distinguishing number of that graph.Algorithm 18.
h
h
h
h
h
Preprocess. Apply Floyd-Warshall algorithm to compute the distance matrix of G.
Step
1 (input: distance matrix). Input is the distance matrix of the graph G of order n.
Step
2 (selection of columns of D to find all the distance pattern distinguishing sets of G). Select all n
×
k
:
1
≤
k
≤
n and k
≠
2 submatrices D
i of D. By Theorem 8, cardinality of a distance pattern distinguishing set is not equal to 2.
Step
3 (formation of distance patterns of vertices in G from the rows of D
i). Make distance patterns of the vertices in G by considering each row of D
′ as sets.Step
4 (identify the distance pattern distinguishing sets). If all the distance patterns are distinct, then a set of vertices M corresponding to the columns in D
′ form the distance pattern distinguishing set. Otherwise, M is not a distance pattern distinguishing set.Step
5 (find distance pattern distinguishing number of G). If there is no distance pattern distinguishing set for G, then distance pattern distinguishing number of G is zero. Otherwise, distance pattern distinguishing number of G is the minimum cardinality of distance pattern distinguishing sets.The following examples illustrate the correctness and efficiency of the algorithm given above.Example 19.
By Theorem8, the distance pattern distinguishing number of a path is 1. Now we calculate the same for P
3 of Figure 2 using the above algorithm.
Step
1 (input: distance matrix of P
3). Consider
(11)
D
=
(
0
1
2
1
0
1
2
1
0
)
.
Step
2 (selection of all 3
×
k
:
1
≤
k
≤
3 and k
≠
2 submatrices of D). Consider
(12)
D
1
=
(
0
1
2
)
,
D
2
=
(
1
0
1
)
,
D
3
=
(
2
1
0
)
,
D
4
=
(
0
1
2
1
0
1
2
1
0
)
.
Step
3 (formation of distance patterns of vertices of P
3 from the rows of above submatrices). Possible distance patterns of the vertices of P
3 are D
1
′
=
{
{
0
}
,
{
1
}
,
{
2
}
}, D
2
′
=
{
{
1
}
,
{
0
}
,
{
1
}
}, D
3
′
=
{
{
2
}
,
{
1
}
,
{
0
}
}, and D
4
′
=
{
{
0,1
,
2
}
,
{
0,1
}
,
{
0,1
,
2
}
}.
Step
4 (identify the distance pattern distinguishing sets from Step 3). From Step 3, D
1
′ and D
3
′ give distinct distance patterns for the vertices of P
3 and hence either the vertices v
1 or v
3 forms a distance pattern distinguishing set.
Step
5 (find distance pattern distinguishing number of G). From Step 4, distance pattern distinguishing number of P
3 is 1.Figure 2Example 20.
By Theorem6, the cycle C
4 is not a distance pattern distinguishing graph.
Step
1 (input: distance matrix of C
4). Consider
(13)
D
=
(
0
1
2
1
1
0
1
2
2
1
0
1
1
2
1
0
)
.
Step
2 (selection of all 4
×
k
:
1
≤
k
≤
4 and k
≠
2 submatrices of D). Consider
(14)
D
1
=
(
0
1
2
1
)
,
D
2
=
(
1
0
1
2
)
,
D
3
=
(
2
1
0
1
)
,
D
4
=
(
1
2
1
0
)
,
D
5
=
(
0
1
2
1
0
1
2
1
0
1
2
1
)
,
D
6
=
(
0
1
1
1
0
2
2
1
1
1
2
0
)
,
D
7
=
(
0
2
1
1
1
2
2
0
1
1
1
0
)
,
D
8
=
(
1
2
1
0
1
2
1
0
1
2
1
0
)
,
D
9
=
(
0
1
2
1
1
0
1
2
2
1
0
1
1
2
1
0
)
.
Step
3 (formation of distance patterns of vertices of P
3 from the rows of above submatrices). Possible distance patterns of the vertices of P
3 are
(15)
D
1
′
=
{
{
0
}
,
{
1
}
,
{
2
}
,
{
1
}
}
,
D
2
′
=
{
{
1
}
,
{
0
}
,
{
1
}
,
{
2
}
}
,
D
3
′
=
{
{
2
}
,
{
1
}
,
{
0
}
,
{
1
}
}
,
D
4
′
=
{
{
1
}
,
{
2
}
,
{
0
}
,
{
1
}
}
,
D
5
′
=
{
{
0,1
,
2
}
,
{
0,1
}
,
{
0,1
,
2
}
,
{
1,2
}
}
,
D
6
′
=
{
{
0,1
}
,
{
0,1
,
2
}
,
{
1,2
}
,
{
0,1
,
2
}
}
,
D
7
′
=
{
{
0,1
,
2
}
,
{
1,2
}
,
{
0,1
,
2
}
,
{
0,1
}
}
,
D
8
′
=
{
{
1,2
}
,
{
0,1
,
2
}
,
{
0,1
}
,
{
0,1
,
2
}
}
,
D
9
′
=
{
{
0,1
,
2
}
,
{
0,1
,
2
}
,
{
0,1
,
2
}
,
{
0,1
,
2
}
}
.
Step
4 (identify the distance pattern distinguishing sets from Step 3). From Step 3, it can be seen that at least one set is repeated in all the above given distance patterns. Hence, C
4 has no distance pattern distinguishing sets.Remark 21.
An R program has been developed based on this algorithm and calculated the distance pattern distinguishing number of several classes of graphs. The same program tested whether the input graph is distance pattern distinguishing graph or not.



---

*Source: 328703-2014-06-11.xml*