Document Type

Article

Publication Date

2014

Publication Source

The Electronic Journal of Combinatorics

Volume

21

Issue

3

Abstract

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.

Keywords

Graph automorphism; regular graph; regularization

Disciplines

Mathematics

Included in

Mathematics Commons

Share

COinS