A partial refining of the Erdos-Kelly regulation

• Autorzy: Górska Joanna , Skupień Zdzisław

Identyfikatory

DOI

10.7494/OpMath.2019.39.3.355

• Języki publikacji: EN

Abstrakty

EN

The aim of this note is to advance the refining of the Erdos-Kelly result on graphical inducing regularization. The operation of inducing regulation (on graphs or multigraphs) with prescribed maximum vertex degree is originated by D. Konig 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. Erdos 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 Δ, the exact minimum number, say 0 = 0(G), of new vertices in a Δ-regular graph H which includes G as an induced subgraph. The number 0(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 ≥ 4, e.g. then the edge-deleted complete graph Kn — e has 0 = n. For n ≥ 4, we present all factors of Kn with 6 = n and next 0 = n — 1. Therein in case 0 = n — 1 and n odd only, we show that a specific extra structure, non-matching, is required. Keywords: inducing A-regulation, cost of regulation.

Słowa kluczowe

EN

inducing A-regulation; cost of regulation

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2019
• Tom: Vol. 39, no. 3
• Strony: 355--360
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Górska Joanna

• AGH University of Science and Technology Faculty of Applied Mathematics al. A. Mickiewicza 30, 30-059 Krakow, Poland

autor

Skupień Zdzisław

• AGH University of Science and Technology Faculty of Applied Mathematics al. A. Mickiewicza 30, 30-059 Krakow, Poland

Bibliografia

• [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 A-regular super-graph of minimum order, Discrete Appl. Math. 131 (2003), 3-9.
• [9] J. Bosak, 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. Erdos, P. Kelly, The minimal regular graph containing a given graph, Amer. Math. Monthly 70 (1963), 1074-1075.
• [14] P. Erdos, 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. Gorska, Z. Skupien, Inducing regularization of graphs, rnultigraphs and pseudographs, Ars Combin. 65 (2002), 129-133.
• [16] J. Gorska, Z. Skupien, Erratum to: "Inducing regularization of graphs, multigraphs and pseudographs" [Ars Cornbin. 65 (2002) 129-133], Ars Combin. 82 (2007), 381-382.
• [17] J. Gorska, Z. Skupien, Inducing regularization of any digraphs, Discrete Appl. Math. 157 (2009), 947-952.
• [18] F. Harary, Graph Theory, Addison-Wesley, Reading, 1969.
• [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. Konig, (Iber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916), 453-465.
• [22] D. Konig, Theorie der endlichen und unendlichen Graphen, Akad. Verlagsgesell., Leipzig, 1936 (Reprinted by Teubner, Leipzig, 1986).