Kronecker Products, Polarity Quotients and Large Graph Constructions
Kelly Isham, Kartik Lakhotia, Laura Monroe, Fabrizio Petrini
Source abstract
In this paper, we establish a structural compatibility between the Kronecker product of bipartite graphs that admit polarity and their polarity quotient, and provide a sharp upper bound on the diameter of these graphs. For certain factor graphs, the diameter of the Kronecker product meets the upper bound on diameter, among them the generalized polygons. Generalized polygons with their polarity quotients have been notably used in the past to construct very large graphs. We apply the structural theorems in the paper to generalized polygons $\mathbb{G}_n(q,q)$ used as factor graphs, and build three new families of graphs of large order covering an infinite but sparse set of degrees, one of diameter $2$, one of diameter $3$ and one of diameter $5$. These asymptotically approach a theoretical upper bound on graph size as orders $q$ and $r$ of the generalized polygon factors increase. As an example, we develop one such family, derived from generalized quadrangles, and construct new diameter-$3$ graphs of low degree that are larger than any previously known at their degrees.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.