On the diameter of the Kronecker product graph

Fu-Tao Hu; Jun-Ming Xu

paper

On the diameter of the Kronecker product graph

arXiv:1204.4014

Abstract

Let $G_{1}$ and $G_{2}$ be two undirected nontrivial graphs. The Kronecker product of $G_{1}$ and $G_{2}$ denoted by $G_{1} \otimes G_{2}$ with vertex set $V (G_{1}) \times V (G_{2})$ , two vertices $x_{1} x_{2}$ and $y_{1} y_{2}$ are adjacent if and only if $(x_{1}, y_{1}) \in E (G_{1})$ and $(x_{2}, y_{2}) \in E (G_{2})$ . This paper presents a formula for computing the diameter of $G_{1} \otimes G_{2}$ by means of the diameters and primitive exponents of factor graphs.

9 pages, 18 references

References in corpus (1)

Kronecker Graphs: An Approach to Modeling Networks