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.
Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies
Informacja
SZANOWNI CZYTELNICY!
UPRZEJMIE INFORMUJEMY, ŻE BIBLIOTEKA FUNKCJONUJE W NASTĘPUJĄCYCH GODZINACH:
Wypożyczalnia i Czytelnia Główna: poniedziałek – piątek od 9.00 do 19.00