The Kronecker product of graphs 论文

摘要

Introduction. This note considers a product derived from the Kronecker product of matrices. Some indication of the geometrical nature of this product is given and a theorem stating necessary and sufficient conditions for a product to be connected is proved. The matrix analogue of the above result is also stated. I. A convenient representation for a finite undirected [1] G is an adjacency matrix. If the vertex set of G is { Pi }, i = 1, , then an adjacency matrix of G is an nXn matrix (aij) with ai1 equal to the number of lines (paths of length one) joining pi to pj. A given is then represented by an equivalence class of matrices A= { PiAPi-l for all permutation matrices Pi of order equal to the order of A }. Each element of A: corresponds to a different ordering of the vertices of G. It is clear that for each such class of adjacency matrices there corresponds a unique class of isomorphic graphs. From this point on graph will mean a finite undirected with no loops. Such a has an adjacency matrix (ai0) whose entries are non-negative integers such that aij=aji and ai=0. We also use the following notation: o(G) is the number of vertices of G and is called the order of G, pLp7, is a chain in G from vertex Pi to vertex Pk, and n(pl->pk) is the number of lines (not necessarily distinct) in PlPk. If A and B are two adjacency matrices and A o B is some matrix product which is also an adjacency matrix then this matrix operation