The CNs Tensor Product of Graphs: Structure, Spectra and Application

Abstract

In this study, we present a product graph called CNs tensor product based on the concept of CNs vertices—those with identical neighborhoods. The structure of this product graph is closely tied to the CN sets—induced by equivalence among CNs vertices, of the factor graphs, giving rise to multipartite components which are the complements of Rook's graphs and isolated vertices. Also, the spectral analysis reveals that the adjacency matrix of the product graph is the kronecker product of the CNs matrices of the factor graphs, leading to an integral spectrum. Moreover, we examine the Laplacian and Signless Laplacian spectrum of the product graph. This framework also offers insight into biological applications such as homology modeling, where proteins are represented as graphs. The automorphism group of the CNs tensor product reflects the symmetries inherited from its factor graphs, and can be written in terms of the symmetric groups corresponding to the sizes of CN sets with more than one element. We also analyze the independence number, matching number, and chromatic number of the product graph, showing that they are influenced by the structure of the multipartite components and the distribution of isolated vertices.