Opuscula Math. 39, no. 3 (2019), 355-360
https://doi.org/10.7494/OpMath.2019.39.3.355

Opuscula Mathematica

# A partial refining of the Erdős-Kelly regulation

Joanna Górska
Zdzisław Skupień

Abstract. 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.

Keywords: inducing $$\Delta$$-regulation, cost of regulation.

Mathematics Subject Classification: 05C35, 05C75.

Full text (pdf)

1. J. Akiyama, F. Harary, The regulation number of a graph, Publ. Inst. Math. (Beograd) (N.S.) 34 (1983) 48, 3-5.
2. J. Akiyama, H. Era, F. Harary, Regular graphs containing a given graph, Elem. Math. 38 (1983), 15-17.
3. L.W. Beineke, R.E. Pippert, Minimal regular extensions of oriented graphs, Amer. Math. Monthly 76 (1969), 145-151.
4. C. Berge, Regularisable graphs, Ann. Discrete Math. 3 (1978), 11-19.
5. C. Berge, Regularisable graphs I, Discrete Math. 23 (1978), 85-89.
6. C. Berge, Regularisable graphs II, Discrete Math. 23 (1978), 91-95.
7. A. Blass, G. Exoo, F. Harary, Paley graphs satisfy all first order adjacency axioms, J. Graph Theory 5 (1981), 435-439.
8. H.L. Bodlaender, R.B. Tan, J. van Leeuwen, Finding a $$\Delta$$-regular supergraph of minimum order, Discrete Appl. Math. 131 (2003), 3-9.
9. J. Bosák, The review of [14] (and [13]), MR 36 # 6312; reprinted in: W.G. Brown, ed., Reviews in Graph Theory, Amer. Math. Soc., Providence, RI, 1980; vol. 1, p. 195.
10. F. Buckley, Regularizing irregular graphs, Math. Comput. Modelling 17 (1993) 11, 29-33.
11. G. Chartrand, L. Lesniak, Graphs & Digraphs, Chapman & Hall, London, 1996.
12. G. Chartrand, C.E. Wall, On regular bipartite-preserving supergraphs, Aequat. Math. 13 (1975) 1/2, 97-101.
13. P. Erdős, P. Kelly, The minimal regular graph containing a given graph, Amer. Math. Monthly 70 (1963), 1074-1075.
14. P. Erdős, P. Kelly, The minimal regular graph containing a given graph, [in:] F. Harary, L.W. Beineke (eds.), A Seminar on Graph Theory, Holt, Rinehart and Winston, New York, 1967, 65-69.
15. J. Górska, Z. Skupień, Inducing regularization of graphs, multigraphs and pseudographs, Ars Combin. 65 (2002), 129-133.
16. J. Górska, Z. Skupień, Erratum to: "Inducing regularization of graphs, multigraphs and pseudographs" [Ars Combin. 65 (2002) 129-133], Ars Combin. 82 (2007), 381-382.
17. J. Górska, Z. Skupień, Inducing regularization of any digraphs, Discrete Appl. Math. 157 (2009), 947-952.
19. F. Jaeger, C. Payan, A class of regularisable graphs, Ann. Discrete Math. 3 (1978), 125-128.
20. R. Jajcay, D. Mesner, Embedding arbitrary finite simple graphs into small strongly regular graphs, J. Graph Theory 34 (2000), 1-8.
21. D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916), 453-465.
22. D. König, Theorie der endlichen und unendlichen Graphen, Akad. Verlagsgesell., Leipzig, 1936 (Reprinted by Teubner, Leipzig, 1986).
• Joanna Górska
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. A. Mickiewicza 30, 30-059 Krakow, Poland
• Zdzisław Skupień
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. A. Mickiewicza 30, 30-059 Krakow, Poland
• Communicated by Gyula O.H. Katona.
• Revised: 2018-01-25.
• Accepted: 2018-09-05.
• Published online: 2019-02-23.