Open AccessA partial refining of the Erdős-Kelly regulation
Author(s) -
Joanna Górska,
Zdzisław Skupień
Publication year - 2019
Publication title -
rocznik akademii górniczo-hutniczej im. stanisława staszica. opuscula mathematica/opuscula mathematica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.481
H-Index - 16
eISSN - 2300-6919
pISSN - 1232-9274
DOI - 10.7494/opmath.2019.39.3.355
Subject(s) - combinatorics , mathematics , iterated function , vertex (graph theory) , bounded function , graph , upper and lower bounds , discrete mathematics , mathematical analysis
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.