The Electronic Journal of Combinatorics
Let G be a finite simple graph of order n, maximum degree Δ, and minimum degree δ. A compact regularization of G is a Δ-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 mcr(G) denote the index of a minimum compact regularization of G and let mcsr(G) denote the index of a minimum compact symmetric regularization of G.
Erdős and Kelly proved that every graph G has a compact regularization and mcr(G)≤2. Building on a result of König, Chartrand and Lesniak showed that every graph has a compact symmetric regularization and mcsr(G)≤2Δ−δ. Using a partial Cartesian product construction, we improve this to mcsr(G)≤Δ−δ+2 and give examples to show this bound cannot be reduced below Δ−δ+1.
Graph automorphism; regular graph; regularization
Robert Vandell, Matthew Walsh, and William D. Weakley (2014).
On Compact Symmetric Regularizations of Graphs. The Electronic Journal of Combinatorics.21 (3).