Hamming index of graphs with respect to its incidence matrix

Harishchandra S. Ramane, Ishwar B. Baidari, Raju B. Jummannaver, Vinayak V. Manjalapur, Gouramma A. Gudodagi, Ashwini S. Yalnaik, Ajith S. Hanagawadimath


Let $B(G)$ be the incidence matrix of a graph $G$. The row in $B(G)$ corresponding to a vertex $v$, denoted by $s(v)$ is the string which belongs to $\Bbb{Z}_2^n$, a set of $n$-tuples over a 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 we obtain the Hamming distance between the strings generated by the incidence matrix of a graph. The sum of Hamming distances between all pairs of strings, called Hamming index of a graph is obtained.


Hamming distance; strings; incidence matrix; Hamming index

Full Text:


DOI: http://dx.doi.org/10.19184/ijc.2022.6.2.4


A. B. Ganagi, H. S. Ramane, Hamming distance between the strings generated by adjacency matrix of a graph and their sum, Algebra Discrete Math. 22 (2016), 82-93.

F. Harary, Graph Theory, Addison-Wesley, Reading, 1969.

W. Imrich, S. Klavzar, A simple O(mn) algorithm for recognizing Hamming graphs, Bull. Inst. Combin. Appl. 9 (1993), 45-56.

S. Klavzar, I. Peterin, Characterizing subgraphs of Hamming graphs, J. Graph Theory 49 (2005), 302-312.

B. Kolman, R. Busby, S. C. Ross, Discrete Mathematical Structures, Prentice Hall of India, New Delhi, 2002.

H. S. Ramane, A. B. Ganagi, Hamming index of class of graphs, Int. J. Curr. Engg. Tech., (2013), 205-208.

H. S. Ramane, V. B. Joshi, R. B. Jummannaver, V. V. Manjalapur, S. C. Patil, S. D. Shindhe, V. S. Hadimani, V. K. Kyalkonda, B. C. Baddi, Hamming index of a graph generated by an edge-vertex incidence matrix, Int. J. Math. Sci. Engg. Appl. 9 (2015), 93-103.


  • There are currently no refbacks.

ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats