On compact symmetric regularizations of graphs

R. Vandell¹ ; M. Walsh¹ ; W. D. Weakley¹

¹Department of Mathematical Sciences Indiana University-Purdue University at Fort Wayne Fort Wayne, IN 46805

The electronic journal of combinatorics, Tome 21 (2014) no. 3

Résumé

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 $\mbox{mcr}(G)$ denote the index of a minimum compact regularization of $G$ and let $\mbox{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 $\mbox{mcr}(G) \leq 2$. Building on a result of König, Chartrand and Lesniak showed that every graph has a compact symmetric regularization and $\mbox{mcsr}(G) \leq 2^{\Delta - \delta}$. Using a partial Cartesian product construction, we improve this to $\mbox{mcsr}(G) \leq \Delta - \delta + 2$ and give examples to show this bound cannot be reduced below $\Delta - \delta + 1$.

Détail

DOI : 10.37236/3821

Classification : 05C60, 05C07, 05C35, 05C76
Mots-clés : graph automorphism, regular graph, regularization