Geodesic
Hamming distance between the strings generated by adjacency matrix of a graph and their sum
Algebra and discrete mathematics, Tome 22 (2016) no. 1, pp. 82-93.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $\mathbb{Z}_2^n$ 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 $H_A(G)$, the sum of the Hamming distances between all pairs of strings generated by the adjacency matrix is obtained for some graphs.
Keywords: Hamming distance, string, adjacency matrix. 
@article{ADM_2016_22_1_a4,
     author = {Asha B. Ganagi and Harishchandra S. Ramane},
     title = {Hamming distance between the strings generated by adjacency matrix of a graph and their sum},
     journal = {Algebra and discrete mathematics},
     pages = {82--93},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADM_2016_22_1_a4/}
}
TY  - JOUR
AU  - Asha B. Ganagi
AU  - Harishchandra S. Ramane
TI  - Hamming distance between the strings generated by adjacency matrix of a graph and their sum
JO  - Algebra and discrete mathematics
PY  - 2016
SP  - 82
EP  - 93
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ADM_2016_22_1_a4/
LA  - en
ID  - ADM_2016_22_1_a4
ER  - 
%0 Journal Article
%A Asha B. Ganagi
%A Harishchandra S. Ramane
%T Hamming distance between the strings generated by adjacency matrix of a graph and their sum
%J Algebra and discrete mathematics
%D 2016
%P 82-93
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ADM_2016_22_1_a4/
%G en
%F ADM_2016_22_1_a4
Asha B. Ganagi; Harishchandra S. Ramane. Hamming distance between the strings generated by adjacency matrix of a graph and their sum. Algebra and discrete mathematics, Tome 22 (2016) no. 1, pp. 82-93. http://geodesic.mathdoc.fr/item/ADM_2016_22_1_a4/

[1] S. Bang, E. R. van Dam, J. H. Koolen, “Spectral characterization of the Hamming graphs”, Linear Algebra Appl., 429 (2008), 2678–2686 | DOI | MR | Zbl

[2] V. Chepoi, “$d$-connectivity and isometric subgraphs of Hamming graphs”, Cybernetics, 1 (1988), 6–9 | DOI | MR

[3] F. Harary, Graph Theory, Addison-Wesley, Reading, 1969 | MR | Zbl

[4] W. Imrich, S. Klavžar, “A simple $O(mn)$ algorithm for recognizing Hamming graphs”, Bull. Inst. Combin. Appl., 9 (1993), 45–56 | MR | Zbl

[5] W. Imrich, S. Klavžar, “On the complexity of recognizing Hamming graphs and related classes of graphs”, European J. Combin., 17 (1996), 209–221 | DOI | MR | Zbl

[6] W. Imrich, S. Klavžar, “Recognizing Hamming graphs in linear time and space”, Inform. Process. Lett., 63 (1997), 91–95 | DOI | MR | Zbl

[7] S. Klavžar, I. Peterin, “Characterizing subgraphs of Hamming graphs”, J. Graph Theory, 49 (2005), 302–312 | DOI | MR | Zbl

[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), 63–74 | DOI | MR | Zbl

[10] B. Park, Y. Sano, “The competition numbers of Hamming graphs with diameter at most three”, J. Korean Math. Soc., 48 (2011), 691–702 | DOI | MR | Zbl

[11] R. Squier, B. Torrence, A. Vogt, “The number of edges in a subgraph of a Hamming graph”, Appl. Math. Lett., 14 (2001), 701–705 | DOI | MR | Zbl

[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), 179–197 | DOI | MR | Zbl

[14] P. Winkler, “Isometric embeddings in products of complete graphs”, Discrete Appl. Math., 7 (1984), 221–225 | DOI | MR | Zbl