Hamming distance between the strings generated by adjacency matrix of a graph and their sum
Let A(G) be the adjacency matrix of a graph G. Denote by s(v) the row of the adjacency matrix corresponding to the vertex v of G. It is a string in the set Zn2 of all n-tuples over the field of order two. The Hamming distance between the strings s(u) and s(v) is the number of positions in which s(u)...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2016
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/155746 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Hamming distance between the strings generated by adjacency matrix of a graph and their sum / A.B. Ganagi, H.S. Ramane // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 1. — С. 82-93. — Бібліогр.: 14 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-155746 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1557462019-06-18T01:25:35Z Hamming distance between the strings generated by adjacency matrix of a graph and their sum Ganagi, A.B. Ramane, H.S. Let A(G) be the adjacency matrix of a graph G. Denote by s(v) the row of the adjacency matrix corresponding to the vertex v of G. It is a string in the set Zn2 of all n-tuples over the field of order two. The Hamming distance between the strings s(u) and s(v) is the number of positions in which s(u) and s(v) differ. In this paper the Hamming distance between the strings generated by the adjacency matrix is obtained. Also HA(G), the sum of the Hamming distances between all pairs of strings generated by the adjacency matrix is obtained for some graphs. 2016 Article Hamming distance between the strings generated by adjacency matrix of a graph and their sum / A.B. Ganagi, H.S. Ramane // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 1. — С. 82-93. — Бібліогр.: 14 назв. — англ. 1726-3255 2010 MSC:05C99. http://dspace.nbuv.gov.ua/handle/123456789/155746 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
Let A(G) be the adjacency matrix of a graph G. Denote by s(v) the row of the adjacency matrix corresponding to the vertex v of G. It is a string in the set Zn2 of all n-tuples over the field of order two. The Hamming distance between the strings s(u) and s(v) is the number of positions in which s(u) and s(v) differ. In this paper the Hamming distance between the strings generated by the adjacency matrix is obtained. Also HA(G), the sum of the Hamming distances between all pairs of strings generated by the adjacency matrix is obtained for some graphs. |
| format |
Article |
| author |
Ganagi, A.B. Ramane, H.S. |
| spellingShingle |
Ganagi, A.B. Ramane, H.S. Hamming distance between the strings generated by adjacency matrix of a graph and their sum Algebra and Discrete Mathematics |
| author_facet |
Ganagi, A.B. Ramane, H.S. |
| author_sort |
Ganagi, A.B. |
| title |
Hamming distance between the strings generated by adjacency matrix of a graph and their sum |
| title_short |
Hamming distance between the strings generated by adjacency matrix of a graph and their sum |
| title_full |
Hamming distance between the strings generated by adjacency matrix of a graph and their sum |
| title_fullStr |
Hamming distance between the strings generated by adjacency matrix of a graph and their sum |
| title_full_unstemmed |
Hamming distance between the strings generated by adjacency matrix of a graph and their sum |
| title_sort |
hamming distance between the strings generated by adjacency matrix of a graph and their sum |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2016 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/155746 |
| citation_txt |
Hamming distance between the strings generated by adjacency matrix of a graph and their sum / A.B. Ganagi, H.S. Ramane // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 1. — С. 82-93. — Бібліогр.: 14 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT ganagiab hammingdistancebetweenthestringsgeneratedbyadjacencymatrixofagraphandtheirsum AT ramanehs hammingdistancebetweenthestringsgeneratedbyadjacencymatrixofagraphandtheirsum |
| first_indexed |
2025-07-14T07:59:15Z |
| last_indexed |
2025-07-14T07:59:15Z |
| _version_ |
1837608422542934016 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 22 (2016). Number 1, pp. 82–93
© Journal “Algebra and Discrete Mathematics”
Hamming distance between the strings
generated by adjacency matrix of a graph
and their sum
Asha B. Ganagi and Harishchandra S. Ramane
Communicated by D. Simson
Abstract. Let A(G) be the adjacency matrix of a graph G.
Denote by s(v) the row of the adjacency matrix corresponding to
the vertex v of G. It is a string in the set Zn
2
of all n-tuples over the
field of order two. The Hamming distance between the strings s(u)
and s(v) is the number of positions in which s(u) and s(v) differ.
In this paper the Hamming distance between the strings generated
by the adjacency matrix is obtained. Also HA(G), the sum of the
Hamming distances between all pairs of strings generated by the
adjacency matrix is obtained for some graphs.
1. Introduction
Let Z2 = {0, 1} and (Z2, +) be the additive group, where + denotes
addition modulo 2. For any positive integer n,
Z
n
2 = Z2 × Z2 × · · · × Z2 (n factors)
= {(x1, x2, . . . , xn)|x1, x2, . . . , xn ∈ Z2}.
Thus every element of Z
n
2 is an n-tuple (x1, x2, . . . , xn) written as
x = x1x2 . . . xn where every xi is either 0 or 1 and is called a string or
word. The number of 1’s in x = x1x2 . . . xn is called the weight of x and
is denoted by wt(x).
2010 MSC: 05C99.
Key words and phrases: Hamming distance, string, adjacency matrix.
A. B. Ganagi, H. S. Ramane 83
Let x = x1x2 . . . xn and y = y1y2 . . . yn be the elements of Zn
2 . Then
the sum x + y is computed by adding the corresponding components of
x and y under addition modulo 2. That is, xi + yi = 0 if xi = yi and
xi + yi = 1 if xi 6= yi, i = 1, 2, . . . , n.
The Hamming distance Hd(x, y) between the strings x = x1x2 . . . xn
and y = y1y2 . . . yn is the number of i’s such that xi 6= yi, 1 6 i 6 n. Thus
Hd(x, y) = Number of positions in which x and y differ = wt(x + y).
Example 1. Let x = 01001 and y = 11010. Therefore x + y = 10011.
Hence Hd(x, y) = wt(x + y) = 3.
Lemma 1 ([8]). For all x, y, z ∈ Z
n
2 , the following conditions are satisfied:
(i) Hd(x, y) = Hd(y, x);
(ii) Hd(x, y) > 0;
(iii) Hd(x, y) = 0 if and only if x = y;
(iv) Hd(x, z) 6 Hd(x, y) + Hd(y, z).
A graph G with vertex set V (G) is called a Hamming graph [4, 7] if
each vertex v ∈ V (G) can be labeled by a string s(v) of a fixed length
such that Hd(s(u), s(v)) = dG(u, v) for all u, v ∈ V (G), where dG(u, v) is
the length of shortest path joining u and v in G.
Hamming graphs are known as an interesting graph family in connec-
tion with the error-correcting codes and association schemes. For more
details see [1, 2, 4 - 7, 9 - 11, 13, 14].
Motivated by the work on Hamming graphs, in this paper we study
the Hamming distance between the strings generated by the adjacency
matrix of a graph. Also we obtain the sum of the Hamming distances
between all pairs of strings for certain graphs.
2. Preliminaries
Let G be an undirected graph without loops and multiple edges with
n vertices and m edges. Let V (G) = {v1, v2, . . . , vn} be the vertex set of
G. The vertices adjacent to the vertex v are called the neighbours of v.
The degree of a vertex v, denoted by degG(v) is the number of neighbours
of v. A graph is said to be r-regular if the degree of each vertex is equal
to r. The vertices which are adjacent to both u and v simultaneously
are called the common neghbours of u and v and the vertices which are
neither adjacent to u nor adjacent to v are called non-common neighbours
of u and v. The distance between two vertices u and v in G is the length
of shortest path joining u and v and is denoted by dG(u, v).
84 Hamming distance between the strings
The adjacency matrix of G is a square matrix A(G) = [aij ] of order n,
in which aij = 1 if the vertex vi is adjacent to vj and aij = 0, otherwise.
Denote by s(v) the row of the adjacency matrix corresponding to the
vertex v. It is a string in the set Z
n
2 of all n-tuples over the field of order
two.
Sum of Hamming distances between all pairs of strings generated by
the adjacency matrix of a graph G is denoted by HA(G). That is,
HA(G) =
∑
16i<j6n
Hd(s(vi), s(vj)).
HA(G) is a graph invariant. For graph theoretic terminology we refer
to the books [3, 12].
Example 2.
�
�
❅
❅
t t
t
t
v3 v4
v2
v1
Figure 1. Graph G.
Adjacency matrix of a graph G of Fig. 1 is
A(G) =
v1
v2
v3
v4
0 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0
and the strings are s(v1) = 0100, s(v2) = 1011, s(v3) = 0101, s(v4) = 0110.
Hd(s(v1), s(v2)) = 4, Hd(s(v1), s(v3)) = 1, Hd(s(v1), s(v4)) = 1,
Hd(s(v2), s(v3)) = 3, Hd(s(v2), s(v4)) = 3, Hd(s(v3), s(v4)) = 2.
Therefore HA(G) = 4 + 1 + 1 + 3 + 3 + 2 = 14.
3. Hamming distance between strings
In this section we obtain the Hamming distance between a given pair
of strings generated by the adjacency matrix of a graph.
A. B. Ganagi, H. S. Ramane 85
Theorem 1. Let G be a graph with n vertices. Let the vertices u and v
of G have k common neighbours and l non-common neighbours.
(i) If u and v are adjacent vertices, then
Hd(s(u), s(v)) = n − k − l.
(ii) If u and v are nonadjacent vertices, then
Hd(s(u), s(v)) = n − k − l − 2.
Proof. (i) Let u and v be the adjacent vertices of G. Let u and v have k
common neighbours and l non-common neighbours. Therefore remaining
n − k − l − 2 vertices other than u and v are adjacent to either u or v
but not to both. Therefore the strings of u and v from A(G) will be in
the form
s(u) = x1x2x3 . . . xk+1xk+2xk+3 . . . xk+l+2xk+l+3 . . . xn
and
s(v) = y1y2y3 . . . yk+1yk+2yk+3 . . . yk+l+2yk+l+3 . . . yn
where x1 = 0, x2 = 1, y1 = 1, y2 = 0, xi = yi = 1 for i = 3, 4, . . . , k + 2,
xi = yi = 0 for i = k + 3, k + 4, . . . , k + l + 2 and xi 6= yi for i =
k + l + 3, k + l + 4, . . . , n.
Therefore s(u) and s(v) differ at n − k − l − 2 + 2 = n − k − l places.
Hence Hd(s(u), s(v)) = n − k − l.
(ii) Let u and v be the nonadjacent vertices of G. Let u and v have k
common neighbours and l non-common neighbours. Therefore remaining
n − k − l − 2 vertices other than u and v are adjacent to either u or v
but not to both. Therefore the strings of u and v from A(G) will be in
the form
s(u) = x1x2x3 . . . xk+1xk+2xk+3 . . . xk+l+2xk+l+3 . . . xn
and
s(v) = y1y2y3 . . . yk+1yk+2yk+3 . . . yk+l+2yk+l+3 . . . yn
where x1 = 0, x2 = 0, y1 = 0, y2 = 0, xi = yi = 1 for i = 3, 4, . . . , k + 2,
xi = yi = 0 for i = k + 3, k + 4, . . . , k + l + 2 and xi 6= yi for i =
k + l + 3, k + l + 4, . . . , n.
Therefore s(u) and s(v) differ at n − k − l − 2 places. Hence
Hd(s(u), s(v)) = n − k − l − 2.
86 Hamming distance between the strings
Lemma 2. Let G be a graph with n vertices. Let the vertices u and v of
G have k common neighbours and l non-common neighbours.
(i) If u and v are adjacent vertices, then
degG(u) + degG(v) = n + k − l.
(ii) If u and v are nonadjacent vertices, then
degG(u) + degG(v) = n + k − l − 2.
Proof. (i) Let u and v be the adjacent vertices of G. Let u and v have k
common neighbours and l non-common neighbours. Therefore remaining
n − k − l − 2 vertices other than u and v are adjacent to either u or v
but not to both. Therefore
degG(u) + degG(v) = k + k + (n − k − l − 2) + 2 = n + k − l.
(ii) Let u and v be the nonadjacent vertices of G. Let u and v have k
common neighbours and l non-common neighbours. Therefore remaining
n − k − l − 2 vertices other than u and v are adjacent to either u or v
but not to both. Therefore
degG(u) + degG(v) = k + k + (n − k − l − 2) = n + k − l − 2.
Theorem 2. Let G be an r-regular graph with n vertices. Let u and v
be the distinct vertices of G. If u and v have k common neighbours, then
Hd(s(u), s(v)) = 2r − 2k.
Proof. We consider here two cases.
Case 1. Let u and v be the adjacent vertices of G. Let u and v have k com-
mon neighbours and l non-common neighbours. Then by Theorem 1 (i),
Hd(s(u), s(v)) = n − k − l. (1)
But from Lemma 2 (i), 2r = n + k − l. Which implies l = n + k − 2r.
Substituting this in (1),
Hd(s(u), s(v)) = n − k − (n + k − 2r) = 2r − 2k.
Case 2. Let u and v be the nonadjacent vertices of G. Let u and v
have k common neighbours and l non-common neighbours. Then by
Theorem 1 (ii),
Hd(s(u), s(v)) = n − k − l − 2. (2)
A. B. Ganagi, H. S. Ramane 87
But from Lemma 2 (ii), 2r = n+k−l−2. Which implies l+2 = n+k−2r.
Substituting this in (2),
Hd(s(u), s(v)) = n − k − (n + k − 2r) = 2r − 2k.
A connected acyclic graph is called tree.
Theorem 3. Let G be a tree with n vertices. Let u and v be the distinct
vertices of G.
(i) If dG(u, v) 6= 2, then Hd(s(u), s(v)) = degG(u) + degG(v).
(ii) If dG(u, v) = 2, then Hd(s(u), s(v)) = degG(u) + degG(v) − 2.
Proof. (i) Let dG(u, v) 6= 2. We consider here two cases.
Case 1. Let dG(u, v) = 1. Then u and v have zero common neighbours
and n − (degG(u) + degG(v)) non-common neighbours. Therefore from
Theorem 1 (i),
Hd(s(u), s(v)) = n − 0 − [n − (degG(u) + degG(v))]
= degG(u) + degG(v).
Case 2. Let dG(u, v) > 2. Then u and v have zero common neighbours
and n − (degG(u) + degG(v) + 2) non-common neighbours. Therefore from
Theorem 1 (ii),
Hd(s(u), s(v)) = n − 0 − [n − (degG(u) + degG(v) + 2)] − 2
= degG(u) + degG(v).
(ii) Let dG(u, v) = 2. Then u and v have 1 common neighbour and
n − (degG(u) + degG(v) + 1) non-common neighbours. Therefore from
Theorem 1 (ii),
Hd(s(u), s(v)) = n − 1 − [n − (degG(u) + degG(v) + 1)] − 2
= degG(u) + degG(v) − 2.
4. Sum of Hamming distances of some graphs
As usual, by Kn, Pn, Cn and Ka,n−a we denote respectively the com-
plete graph, the path, the cycle and the complete bipartite graph on n
vertices.
Theorem 4. For a complete graph Kn, HA(Kn) = n(n − 1).
88 Hamming distance between the strings
Proof. Complete graph Kn on n vertices is a regular graph of degree n−1.
In a complete graph every pair of adjacent vertices has n − 2 common
neighbours and zero non-common neighbours. Also there is no pair of
nonadjacent vertices.
Therefore from Theorem 2, Hd(s(u), s(v)) = 2(n − 1) − 2(n − 2) = 2
for every pair of vertices u and v of Kn and there are
(n
2
)
such pairs in Kn.
Therefore
HA(Kn) =
∑
{u,v}⊆V (Kn)
Hd(s(u), s(v)) =
∑
(n
2
)
2 = n(n − 1).
Theorem 5. For a complete bipartite graph Kp,q, HA(Kp,q) = pq(p + q).
Proof. The graph Kp,q has n = p + q vertices and m = pq edges. Every
pair of adjacent vertices of Kp,q has zero common neighbours and zero non-
common neighbours. Therefore from Theorem 1 (i), Hd(s(u), s(v)) = p+q
for adjacent vertices u and v.
Let V1 and V2 be the partite sets of the vertices of a graph Kp,q, where
|V1| = p and |V2| = q. Let u and v be the nonadjacent vertices. If u, v ∈ V1
then u and v has q common neighbours and p−2 non-common neighbours.
Therefore from Theorem 1 (ii), Hd(s(u), s(v)) = (p+q)−(q)−(p−2)−2 = 0.
Similarly, if u, v ∈ V2, then Hd(s(u), s(v)) = 0. Therefore
HA(Kp,q) =
∑
dG(u,v)=1
Hd(s(u), s(v)) +
∑
dG(u,v) 6=1
Hd(s(u), s(v))
=
∑
m
(p + q) = m(p + q) = pq(p + q).
Theorem 6. For a cycle Cn on n > 3 vertices, HA(Cn) = 2n(n − 2).
Proof. For n = 3 and n = 4, the result follows from the Theorems 4 and 5
respectively. Now we prove for n > 5. Cycle Cn is a regular graph of degree
r = 2. In Cn, n > 5, every pair of adjacent vertices has zero common
neighbours. Therefore from Theorem 2, Hd(s(u), s(v)) = 2r − 0 = 4 for
every pair of adjacent vertices u and v of Cn.
Let dCn
(u, v) = 2. Then u and v have 1 common neighbour. Therefore
from Theorem 2, Hd(s(u), s(v)) = 2r − 2 = 2.
Let dCn
(u, v) > 3. Then u and v have zero common neighbours.
Therefore from Theorem 2, Hd(s(u), s(v)) = 2r − 0 = 4.
A. B. Ganagi, H. S. Ramane 89
Therefore
HA(Cn) =
∑
dCn
(u,v)=1
Hd(s(u), s(v)) +
∑
dCn
(u,v)=2
Hd(s(u), s(v))
+
∑
dCn
(u,v)>2
Hd(s(u), s(v))
= m(4) + n(2) +
((
n
2
)
− m − n
)
(4) = 2n(n − 2).
A graph G is said to be strongly regular with parameters (n, r, a, b) if
it is non complete r-regular graph with n vertices in which every pair of
adjacent vertices has a common neighbours and every pair of nonadjacent
vertices has b common neighbours.
Theorem 7. Let G be a strongly regular graph with parameters (n, r, a, b).
Then HA(G) = n(n − 1)(r − b) + nr(b − a).
Proof. Let G be a strongly regular graph with parameters (n, r, a, b) and
m edges.
From Theorem 2, Hd(s(u), s(v)) = 2r − 2a, if u and v are adjacent
vertices and Hd(s(u), s(v)) = 2r − 2b, if u and v are nonadjacent vertices.
Therefore
HA(G) =
∑
dG(u,v)=1
Hd(s(u), s(v)) +
∑
dG(u,v) 6=1
Hd(s(u), s(v))
=
∑
m
(2r − 2a) +
∑
(n
2
)−m
(2r − 2b)
= m(2r − 2a) +
((
n
2
)
− m
)
(2r − 2b)
=
nr
2
(2r − 2a) +
((
n
2
)
−
nr
2
)
(2r − 2b)
= n(n − 1)(r − b) + nr(b − a).
Theorem 8. Let G be a graph with n vertices and m edges and G be the
complement of G. Then
HA(G) = HA(G) + n(n − 1) − 4m. (3)
Proof. Let u and v be the vertices of G. If the adjacent vertices u and v
have k1 common neighbours and l1 non-common neighbours in G, then
90 Hamming distance between the strings
from Theorem 1 (i)
Hd(s(u), s(v)) = n − k1 − l1. (4)
Further, if the nonadjacent vertices u and v have k2 common neigh-
bours and l2 non-common neighbours in G, then from Theorem 1 (ii)
Hd(s(u), s(v)) = n − k2 − l2 − 2. (5)
Therefore
HA(G) =
∑
dG(u,v)=1
Hd(s(u), s(v)) +
∑
dG(u,v) 6=1
Hd(s(u), s(v))
=
∑
dG(u,v)=1
(n − k1 − l1) +
∑
dG(u,v) 6=1
(n − k2 − l2 − 2)
=
∑
dG(u,v)=1
(n−k1−l1) +
∑
dG(u,v) 6=1
(n−k2−l2)−2
((
n
2
)
−m
)
. (6)
If the vertices u and v are adjacent (nonadjacent) in G, then they
are nonadjacent (adjacent) in G. Therefore from (4) and (5), in G,
Hd(s(u), s(v)) = n − k1 − l1 − 2 for nonadjacent pairs of vertices and
Hd(s(u), s(v)) = n − k2 − l2 for adjacent pairs of vertices. Therefore
HA(G) =
∑
d
G
(u,v) 6=1
Hd(s(u), s(v)) +
∑
d
G
(u,v)=1
Hd(s(u), s(v))
=
∑
d
G
(u,v) 6=1
(n − k1 − l1 − 2) +
∑
d
G
(u,v)=1
(n − k2 − l2)
=
∑
dG(u,v)=1
(n − k1 − l1 − 2) +
∑
dG(u,v) 6=1
(n − k2 − l2)
=
∑
dG(u,v)=1
(n − k1 − l1) − 2m +
∑
dG(u,v) 6=1
(n − k2 − l2). (7)
From (6) and (7) the result follows.
A graph is said to be selfcomplementary if it is isomorphic to its
complement.
Theorem 9. Let G be a graph with n vertices and m edges. Let G
be the complement of G. Then HA(G) = HA(G) if and only if G is
selfcomplementary graph.
A. B. Ganagi, H. S. Ramane 91
Proof. If G is a selfcomplementary graph, then G ∼= G. Therefore
HA(G) = HA(G).
Conversely, let HA(G) = HA(G). Therefore from (3), n(n−1)−4m = 0.
This gives that m = (n(n − 1))/4 implying G is a selfcomplementary
graph [12].
Theorem 10. Let G be a tree on n vertices. Then
HA(G) =
∑
dG(u,v) 6=2
[deg(u) + deg(v)] +
∑
dG(u,v)=2
[deg(u) + deg(v) − 2].
Proof. Follows from the Theorem 3.
Theorem 11. For a path Pn on n > 2 vertices, HA(Pn) = 2n2 − 6n + 6.
Proof. Let v1, v2, . . . , vn be the vertices of Pn where vi is adjacent to vi+1,
i = 1, 2, . . . , n − 1. There are n − 2 pairs of vertices which are at distance
two in Pn. Out of these n − 2 pairs, two pairs (v1, v3) and (vn−2, vn) have
Hamming distance equal to one and the remaining pairs have Hamming
distance 2.
There are
(n
2
)
− (n − 2) pairs of vertices in Pn, which are at distance 1
or at distance greater than 2. Out of these pairs, the one pair (v1, vn) has
Hamming distance 2, 2n − 6 pairs of vertices, in which exactly one vertex
is end vertex, have Hamming distance 3 and the remaining
(n
2
)
− 3n + 7
pairs of vertices have Hamming distance 4. Therefore from Theorem 3,
HA(Pn) =
∑
dPn
(u,v)=2
Hd(s(u), s(v)) +
∑
dPn
(u,v) 6=2
Hd(s(u), s(v))
=
∑
dPn
(u,v)=2
(degPn
(u) + degPn
(v) − 2)
+
∑
dPn
(u,v) 6=2
(degPn
(u) + degPn
(v))
= [2(3 − 2) + (n − 4)(4 − 2)]
+
{
[(1)(2) + (2n−6)(3)] +
[(n
2
)
− (n−2) − (2n−6) − 1
]
(4)
}
= 2n2 − 6n + 6.
5. Conclusion
Theorems 1 and 2 gives the Hamming distance between the strings
generated by adjacency matrix of a graph in terms of number of common
92 Hamming distance between the strings
neighbours and non-common neighbours. Results of Section 4 gives the
sum of Hamming distances between all pairs of strings generated by the
adjacency matrix for some standard graphs like complete graph, complete
bipartite graph, tree, cycle, path, strongly regular graph. Further there
is a scope to extend these reults to graph valued functions such as line
graph, total graph, product graphs.
Acknowledgement
Authors are thankful to Prof. P. R. Hampiholi for his suggestions.
This work was carried out when the author H. S. Ramane was the
employee of Gogte Institute of Technology, Belgaum, India.
References
[1] S. Bang, E. R. van Dam, J. H. Koolen, Spectral characterization of the Hamming
graphs, Linear Algebra Appl., 429, 2008, pp. 2678–2686.
[2] V. Chepoi, d-connectivity and isometric subgraphs of Hamming graphs, Cybernetics,
1, 1988, pp. 6–9.
[3] F. Harary, Graph Theory, Addison-Wesley, Reading, 1969.
[4] W. Imrich, S. Klavžar, A simple O(mn) algorithm for recognizing Hamming graphs,
Bull. Inst. Combin. Appl., 9, 1993, pp. 45–56.
[5] W. Imrich, S. Klavžar, On the complexity of recognizing Hamming graphs and
related classes of graphs, European J. Combin., 17, 1996, pp. 209–221.
[6] W. Imrich, S. Klavžar, Recognizing Hamming graphs in linear time and space,
Inform. Process. Lett., 63, 1997, pp. 91–95.
[7] S. Klavžar, I. Peterin, Characterizing subgraphs of Hamming graphs, J. Graph
Theory, 49, 2005, pp. 302–312.
[8] B. Kolman, R. Busby, S. C. Ross, Discrete Mathematical Structures, Prentice Hall
of India, New Delhi, 2002.
[9] M. Mollard, Two characterizations of generalized hypercubes, Discrete Math., 93,
1991, pp. 63–74.
[10] B. Park, Y. Sano, The competition numbers of Hamming graphs with diameter at
most three, J. Korean Math. Soc., 48, 2011, pp. 691–702.
[11] R. Squier, B. Torrence, A. Vogt, The number of edges in a subgraph of a Hamming
graph, Appl. Math. Lett., 14, 2001, pp. 701–705.
[12] D. B. West, Introduction to Graph Theory, PHI Learning, New Delhi, 2009.
[13] E. Wilkeit, Isometric embeddings in Hamming graphs, J. Combin. Theory Ser. B,
50, 1990, pp. 179–197.
[14] P. Winkler, Isometric embeddings in products of complete graphs, Discrete Appl.
Math., 7, 1984, pp. 221–225.
A. B. Ganagi, H. S. Ramane 93
Contact information
A. B. Ganagi Department of Mathematics,
Gogte Institute of Technology,
Udyambag, Belgaum - 590008, India
E-Mail(s): abganagi@yahoo.co.in
H. S. Ramane Department of Mathematics,
Karnatak University,
Dharwad - 580003, India
E-Mail(s): hsramane@yahoo.com
Received by the editors: 15.08.2013
and in final form 20.08.2014.
|