Hamming distance between the strings generated by adjacency matrix of a graph and their sum

Asha B. Ganagi, Harishchandra S. Ramane

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 \({\Bbb 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

Full Text:

PDF

References


S. Bang, E. R. van Dam, J. H. Koolen, Spectral characterization of the Hamming graphs, Linear Algebra Appl., 429, 2008, pp. 2678-2686.

V. Chepoi, d-connectivity and isometric subgraphs of Hamming graphs, Cybernetics, 1, 1988, pp. 6-9.

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, pp. 45-56.

W. Imrich, S. Klavzar, On the complexity of recognizing Hamming graphs and related classes of graphs, European J. Combin., 17, 1996, pp. 209-221.

W. Imrich, S. Klavzar, Recognizing Hamming graphs in linear time and space, Inform. Process. Lett., 63, 1997, pp. 91-95.

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

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

M. Mollard, Two characterizations of generalized hypercubes, Discrete Math., 93, 1991, pp. 63-74.

B. Park, Y. Sano, The competition numbers of Hamming graphs with diameter at most three, J. Korean Math. Soc., 48, 2011, pp. 691-702.

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.

D. B. West, Introduction to Graph Theory, PHI Learning, New Delhi, 2009.

E. Wilkeit, Isometric embeddings in Hamming graphs, J. Combin. Theory Ser. B, 50, 1990, pp. 179-197.

P. Winkler, Isometric embeddings in products of complete graphs, Discrete Appl. Math., 7, 1984, pp. 221-225.


Refbacks

  • There are currently no refbacks.