Article ID Journal Published Year Pages File Type
4650273 Discrete Mathematics 2009 6 Pages PDF
Abstract

We say that two graphs G1G1 and G2G2 with the same vertex set commute if their adjacency matrices commute. In this paper, we find all integers nn such that the complete bipartite graph Kn,nKn,n is decomposable into commuting perfect matchings or commuting Hamilton cycles. We show that there are at most n−1n−1 linearly independent commuting adjacency matrices of size nn; and if this bound occurs, then there exists a Hadamard matrix of order nn. Finally, we determine the centralizers of some families of graphs.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,