On compact symmetric regularizations of graphs
type: Item
instance of: scholarly article
title: On compact symmetric regularizations of graphs
zbMATH Open document ID: 1298.05230
author: D. Kharzeev
published in: The Electronic Journal of Combinatorics
publication date: 2014-09-09T00:00:00Z
full work available at URL: v21i3p31
review text: 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\).
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C76
zbMATH DE Number: 6341632
zbMATH Keywords: graph automorphism
zbMATH Keywords: regular graph
zbMATH Keywords: regularization
MaRDI profile type: Publication
cites work: Regular graphs containing a given graph
cites work: Algebraic Graph Theory
cites work: Q3158579
cites work: Asymmetric graphs
cites work: Q3636213
cites work: Q4039906
cites work: Kneser Representations of Graphs
cites work: Q5762903
cites work: Minimal regular graph containing a given graph
description: scientific article; zbMATH DE number 6341632