On compact symmetric regularizations of graphs (Q740667)

Summary: Let \(G\) be a finite simple graph of order \(n\), maximum degree \(\Delta\), and minimum degree \(\delta\). A compact regularization of \(G\) is a \(\Delta\)-regular graph \(H\) of which \(G\) is an induced subgraph: \(H\) is symmetric if every automorphism of \(G\) can be extended to an automorphism of \(H\). The index \(|H:G|\) of a regularization \(H\) of \(G\) is the ratio \(|V(H)|/|V(G)|\). Let \(\mathrm{mcr}(G)\) denote the index of a minimum compact regularization of \(G\) and let \(\mathrm{mcsr}(G)\) denote the index of a minimum compact symmetric regularization of \(G\). \textit{P. Erdős} and \textit{P. Kelly} [``The minimal regular graph containing a given graph'', Am. Math. Mon. 70, 1074--1075 (1963)] proved that every graph \(G\) has a compact regularization and \(\mathrm{mcr}(G) \leqslant 2\). Building on a result of \textit{D. König} [Theorie der endlichen und unendlichen Graphen. Leipzig: BSB B. G. Teubner Verlagsgesellschaft (1986; Zbl 0608.05002)], \textit{G. Chartrand} and \textit{L. Lesniak} [Graphs and digraphs. Boca Raton, FL: Chapman \& Hall/CRC (2005; Zbl 1057.05001)] showed that every graph has a compact symmetric regularization and \(\mathrm{mcsr}(G) \leqslant 2^{\Delta - \delta}\). Using a partial Cartesian product construction, we improve this to \(\mathrm{mcsr}(G) \leqslant \Delta - \delta + 2\) and give examples to show this bound cannot be reduced below \(\Delta - \delta + 1\).