Pancyklisk graf

En pancyklisk graf er en rettet eller ikke- rettet graf , der indeholder cyklusser af alle mulige længder fra tre til antallet af grafens hjørnepunkter [1] . Pancykliske grafer er en generalisering af Hamiltonske grafer , grafer, der har cyklusser af den maksimalt mulige længde.

Definitioner

En graf med hjørner er pancyklisk, hvis grafen for nogen indeni indeholder en cyklus af længde [1] . En graf er toppunkt-pancyklisk , hvis grafen for et hvilket som helst toppunkt og inden for samme grænser indeholder en længdecyklus indeholdende toppunkt [2] . På samme måde er en graf kant-pancyklisk , hvis den for en hvilken som helst kant og for en hvilken som helst inden for de samme grænser indeholder en længdecyklus, der indeholder kanten [2] . $G$ $n$ $k$ $3\leqslant k\leqslant n$ $G$ $k$ $v$ $k$ $k$ $v$ $e$ $k$ $v$ $e$

En todelt graf kan ikke være pancyklisk, fordi den ikke indeholder cyklusser af nogen ulige længde, men en graf siges at være bipancyklisk, hvis den indeholder cyklusser af alle lige længder fra 4 til [3] . $n$

Plane grafer

En maksimal ydreplanar graf er en graf dannet af en simpel polygon i planet ved at triagularisere dens indre. Enhver maksimal ydreplanær graf er pancyklisk, hvilket kan vises ved induktion. Den ydre side af grafen er en cyklus med n hjørner, og sletning af enhver trekant, der er forbundet med resten af grafen med kun én kant (et blad af træet, der danner den dobbelte triangulariseringsgraf) danner en maksimal ydreplanar graf med et tal mindre af toppunkter, og ved den induktive antagelse har denne graf alle cyklusser af alle resterende længder. Hvis der lægges mere vægt på valget af trekant, der skal fjernes, så viser de samme argumenter det mere strenge resultat, at enhver maksimal ydreplanær graf er toppunkt-pancyklisk [4] . Det samme er tilfældet for grafer, der har en maksimal ydreplanær graf som en spændende undergraf , især for hjul .

En maksimal plan graf er en plan graf, hvor alle flader, inklusive den ydre, er trekanter. En maksimal plan graf er toppunkt-pancyklisk, hvis og kun hvis den indeholder en Hamilton-cyklus [5] - hvis den ikke er Hamilton-cyklus, er den bestemt ikke pancyklisk, og hvis den er Hamilton-cyklus, danner det indre af Hamilton-cyklussen den ydre flade af den maksimale ydreplanære graf ved de samme spidser og kanter, hvortil de tidligere argumenter for ydreplanære grafer kan anvendes [6] . For eksempel i figuren[ hvad? ] viser pancykliciteten af oktaedergrafen , en Hamiltoniansk maksimal plan graf med seks toppunkter. Mere strengt, af samme årsager, hvis en maksimal plan graf har en cyklus af længde , har den cyklusser af alle mindre længder [7] . $k$

Halin-grafer er plane grafer, der er dannet ud fra en plan tegning af et træ uden hjørner af grad to, ved at tilføje en cyklus, der forbinder træets blade. Halin-grafer er ikke nødvendigvis pancykliske, men de er næsten pancykliske i den forstand, at der ikke er nogen cyklus på højst én længde. Længden af den manglende cyklus er nødvendigvis lige. Hvis ingen af de indre hjørner af Halin-grafen har grad tre, så er grafen nødvendigvis pancyklisk [8] .

I 1971 blev det bemærket [1] at mange klassiske betingelser for eksistensen af en Hamilton-cyklus også er tilstrækkelige til pancyklicitet, og derfor blev det antaget, at enhver 4-forbundet plan graf er pancyklisk, men en familie af modeksempler blev hurtigt fundet [ 9] .

Turneringer

En turnering er en rettet graf med en rettet bue mellem et vilkårligt par af hjørner. Intuitivt kan en turnering bruges til at simulere en round robin ved at tegne en bue fra vinder til taber for hvert spil i konkurrencen. En turnering siges at være stærkt forbundet eller blot stærk, hvis og kun hvis den ikke kan opdeles i to ikke-tomme delmængder af tabere og vindere, således at enhver deltager slår enhver deltager i [10] . Enhver stærk turnering er pancyklisk [11] og toppunkt pancyklisk [12] . Hvis en turnering er regulær (enhver deltager har samme antal sejre og tab som andre deltagere), så er den også kant-pancyklisk [13] , men stærke turneringer med fire hjørner kan ikke være kant-pancykliske. $L$ $W$ $W$ $L$

Grafer med et stort antal kanter

Mantels sætning siger, at enhver urettetvertexgraf, der mindst harkanter og ikke har flere kanter eller sløjfer, enten indeholder en trekant eller er en komplet todelt graf . Denne sætning kan styrkes - enhver urettet Hamiltonsk graf med mindstkanter er enten pancyklisk eller den er [1] . $n$ $n^{2}/4$ $K_{n/2,n/2}$ $n^{2}/4$ $K_{n/2,n/2}$

Der er Hamilton-rettede grafer med toppunkter og buer, der ikke er pancykliske, men enhver Hamilton-rettet graf med mindst buer er pancyklisk. Derudover er en strengt forbundet toppunktsgraf, hvor hvert toppunkt mindst har grad (indkommende og udgående buer tælles sammen) enten pancyklisk eller er en komplet todelt graf [14] . $n$ $n(n+1)/2-3$ $n(n+1)/2-1$ $n$ $n$

Grader af en graf

For enhver graf er dens th grad af grafen defineret som en graf på det samme sæt af hjørner, der har en kant mellem to vilkårlige spidser, hvor afstanden mellem ikke overstiger . Hvis vertex 2-forbundet , så er ved Fleischners sætning en Hamiltonsk graf. Påstanden kan styrkes: grafen vil nødvendigvis være toppunkt-pancyklisk [15] . Mere strengt, hvis det er Hamiltonian, er det også pancyklisk [16] . $G$ $k$ ${\displaystyle G^{k))$ $G$ $k$ $G$ $G^{2}$ $G^{2}$

Beregningsmæssig kompleksitet

At teste en graf for pancyklicitet er et NP-komplet problem selv for det specielle tilfælde med 3-forbundne kubiske grafer . Det er også et NP-komplet problem at teste en graf for toppunktpancyklicitet selv for det specielle tilfælde af polyedriske grafer [17] . En NP-fuldendt opgave er også at teste kvadratet af en graf for Hamiltonianitet, og dermed også at teste for pancyklicitet [18] .

Historie

Pancyklicitet blev først udforsket af Harari og Moser i forbindelse med turneringer [19] , såvel som af Muun [20] og Alpach [13] . Begrebet pancyklicitet blev navngivet af Bondi, som udvidede konceptet for urettede grafer [1] .

Noter

↑ 1 2 3 4 5 Bondy, 1971 .
↑ 1 2 Randerath, Schiermeyer, Tewes, Volkmann, 2002 .
↑ Schmeichel, Mitchem, 1982 .
↑ Li, Corneil, Mendelsohn, 2000 , Proposition 2.5.
↑ Helden, 2007 , konsekvens 3.78.
↑ Bernhart, Kainen, 1979 .
↑ Hakimi, Schmeichel, 1979 .
↑ Skowrońska, 1985 .
↑ Malkevitch, 1971 .
↑ Harary og Moser, 1966 , konsekvens 5b.
↑ Harary og Moser, 1966 , sætning 7.
↑ Moon, 1966 , sætning 1.
↑ 12 Alspach , 1967 .
↑ Häggkvist, Thomassen, 1976 , s. 20-40.
↑ Hobbs (1976) .
↑ Fleischner, 1976 .
↑ Li, Corneil, Mendelsohn, 2000 , sætning 2.3 og 2.4.
↑ Underground (1978) .
↑ Harary, Moser, 1966 .
↑ Månen, 1966 .

Litteratur

Brian Alspach. Cykler af hver længde i almindelige turneringer // Canadian Mathematical Bulletin. - 1967. - T. 10 , no. 2 . - S. 283-286 . .
Frank Bernhart, Paul C. Kainen. Bogtykkelsen af en graf // Journal of Combinatorial Theory , Series B. - 1979. - V. 27 , no. 3 . - S. 320-331 . - doi : 10.1016/0095-8956(79)90021-2 . .
JA Bondy. Pancykliske grafer I // Journal of Combinatorial Theory , Series B. - 1971. - V. 11 , no. 1 . - S. 80-84 . - doi : 10.1016/0095-8956(71)90016-5 . .
H. Fleischner. I kvadratet af grafer er Hamiltonicitet og pancyklicitet, Hamiltonsk forbindelse og panforbundethed ækvivalente begreber // Monatshefte für Mathematik. - 1976. - T. 82 , no. 2 . - S. 125-149 . - doi : 10.1007/BF01305995 . .
Roland Haggkvist, Carsten Thomassen. Om pancykliske digrafier // Journal of Combinatorial Theory , Series B. - 1976. - V. 20 , no. 1 . - doi : 10.1016/0095-8956(76)90063-0 . .
SL Hakimi, EF Schmeichel. Om antallet af cyklusser af længden k i en maksimal plan graf // Journal of Graph Theory. - 1979. - T. 3 . - S. 69-86 . - doi : 10.1002/jgt.3190030108 . .
Frank Harary, Leo Moser. Teorien om round robin-turneringer // American Mathematical Monthly . - 1966. - T. 73 , no. 3 . - S. 231-246 . - doi : 10.2307/2315334 . .
Guido Holden. Hamiltonicitet af maksimale plane grafer og plane trianguleringer . - Rheinisch-Westfälischen Technischen Hochschule Aachen, 2007. - (Afhandling). .
Arthur M. Hobbs. Kvadratet af en blok er toppunkt pancyklisk // Journal of Combinatorial Theory . - 1976. - T. 20 , no. 1 . - S. 1-4 . - doi : 10.1016/0095-8956(76)90061-7 . .
Ming-Chu Li, Derek G. Corneil, Eric Mendelsohn. Pancyklicitet og NP-fuldstændighed i plane grafer // Diskret anvendt matematik. - 2000. - T. 98 , no. 3 . - S. 219-225 . - doi : 10.1016/S0166-218X(99)00163-8 . .
Joseph Malkevitch. Seneste tendenser i grafteori. - Springer-Verlag, 1971. - T. 186. - S. 191-195. — (Forelæsningsnotater i matematik). - doi : 10.1007/BFb0059437 . .
JW Månen. Om underturneringer til en turnering // Canadian Mathematical Bulletin. - 1966. - T. 9 , no. 3 . - S. 297-301 . - doi : 10.4153/CMB-1966-038-7 . .
Bert Randerath, Ingo Schiermeyer, Meike Tewes, Lutz Volkmann. Vertex pancykliske grafer // Diskret anvendt matematik. - 2002. - T. 120 , no. 1-3 . - S. 219-237 . - doi : 10.1016/S0166-218X(01)00292-X . .
Edward Schmeichel, John Mitchem. Todelte grafer med cyklusser af alle lige længder // Journal of Graph Theory. - 1982. - T. 6 , no. 4 . - S. 429-439 . - doi : 10.1002/jgt.3190060407 . .
Mirosława Skowronska. Cycles in Graphs / Brian R. Alspach, Christopher D. Godsil. - Elsevier Science Publishers BV, 1985. - T. 27. - S. 179-194. — (Annals of Discrete Mathematics). .
Paris undergrund. På grafer med Hamiltonske kvadrater // Diskret matematik . - 1978. - T. 21 , no. 3 . - S. 323 . - doi : 10.1016/0012-365X(78)90164-4 . .