TY  - JOUR
ID  - Górska2019
LB  - Górska2019
AU  - Górska, Joanna
AU  - Skupień, Zdzisław
TI  - A partial refining of the Erdős-Kelly regulation
ST  - A partial refining of the Erdős-Kelly regulation
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2019
VL  - 39
IS  - 3
SP  - 355
EP  - 360
DO  - https://doi.org/10.7494/OpMath.2019.39.3.355
UR  - https://doi.org/10.7494/OpMath.2019.39.3.355
AB  - The aim of this note is to advance the refining of the Erdős-Kelly result on graphical inducing regularization. The operation of inducing regulation (on graphs or multigraphs) with prescribed maximum vertex degree is originated by D. König in 1916. As is shown by Chartrand and Lesniak in their textbook Graphs & Digraphs (1996), an iterated construction for graphs can result in a regularization with many new vertices. Erdős and Kelly have presented (1963, 1967) a simple and elegant numerical method of determining for any simple \(n\)-vertex graph \(G\) with maximum vertex degree \(\Delta\), the exact minimum number, say \(\theta =\theta(G)\), of new vertices in a \(\Delta\)-regular graph \(H\) which includes \(G\) as an induced subgraph. The number \(\theta(G)\), which we call the cost of regulation of \(G\), has been upper-bounded by the order of \(G\), the bound being attained for each \(n\ge4\), e.g. then the edge-deleted complete graph \(K_n-e\) has \(\theta=n\). For \(n\ge 4\), we present all factors of \(K_n\) with \(\theta=n\) and next \(\theta=n-1\). Therein in case \(\theta=n-1\) and \(n\) odd only, we show that a specific extra structure, non-matching, is required.
KW  - inducing \(\Delta\)-regulation
KW  - cost of regulation
SN  - 1232-9274
ER  -