Pancyklisk graf

En pancyklisk graf  är en riktad eller oriktad graf som innehåller cykler av alla möjliga längder från tre till antalet grafens hörn [1] . Pancykliska grafer är en generalisering av Hamiltonska grafer , grafer som har cykler av största möjliga längd.

Definitioner

En graf med hörn är pancyklisk om, för någon inom, grafen innehåller en längdcykel [1] . En graf är vertex-pancyklisk om grafen för någon vertex och någon inom samma gränser innehåller en längdcykel som innehåller vertex [2] . På liknande sätt är en graf kantpancyklisk om den, för någon kant och för någon inom samma gränser, innehåller en längdcykel som innehåller kanten [2] .

En tvådelad graf kan inte vara pancyklisk eftersom den inte innehåller cykler av någon udda längd, men en graf sägs vara bipancyklisk om den innehåller cykler av alla jämna längder från 4 till [3] .

Plana grafer

En maximal ytterplanär graf  är en graf som bildas av en enkel polygon i planet genom att triagularisera dess inre. Varje maximal ytterplanär graf är pancyklisk, vilket kan visas genom induktion. Den yttre ytan av grafen är en cykel med n hörn, och om du tar bort en triangel som är kopplad till resten av grafen med endast en kant (ett blad på trädet som bildar den dubbla triangulariseringsgrafen) bildar en maximal ytterplanargraf med ett nummer mindre av hörn, och enligt det induktiva antagandet har denna graf alla cykler av alla återstående längder. Om mer uppmärksamhet ägnas åt valet av triangel att ta bort, så visar samma argument det mer rigorösa resultatet att varje maximal ytterplanär graf är vertex-pancyklisk [4] . Detsamma gäller för grafer som har en maximal ytterplanargraf som en spännande subgraf , särskilt för hjul .

En maximal plan graf  är en plan graf där alla ytor, inklusive den yttre, är trianglar. En maximal plan graf är vertex-pancyklisk om och bara om den innehåller en Hamiltonsk cykel [5]  — om den inte är Hamiltonsk är den definitivt inte pancyklisk, och om den är Hamiltonsk, då bildar det inre av Hamiltons cykel den yttre ytan av den maximala ytterplanära grafen vid samma hörn och kanter, till vilka de tidigare argumenten för ytterplanära grafer kan tillämpas [6] . Till exempel i figuren[ vad? ] visar pancykliciteten för oktaedergrafen , en hamiltonsk maximal plan graf med sex hörn. Mer strikt, av samma skäl, om en maximal plan graf har en cykel av längd , har den cykler av alla mindre längder [7] .

Halin-grafer är plana grafer bildade från en plan ritning av ett träd utan hörn av grad två, genom att lägga till en cykel som förbinder trädets löv. Halin-grafer är inte nödvändigtvis pancykliska, men de är nästan pancykliska i den meningen att det inte finns någon cykel av högst en längd. Längden på den saknade cykeln är nödvändigtvis jämn. Om ingen av Halin-grafens inre hörn har grad tre, så är grafen nödvändigtvis pancyklisk [8] .

År 1971 noterades [1] att många klassiska villkor för existensen av en Hamilton-cykel också är tillräckliga för pancyklicitet, och därför antogs det att varje 4-kopplad plan graf är pancyklisk, men en familj av motexempel hittades snart [ 9] .

Turneringar

En turnering  är en riktad graf med en riktad båge mellan valfritt par av hörn. Intuitivt kan en turnering användas för att simulera en round robin genom att dra en båge från vinnare till förlorare för varje spel i tävlingen. En turnering sägs vara starkt ansluten eller helt enkelt stark om och bara om den inte kan delas upp i två icke-tomma delmängder av förlorare och vinnare, så att vilken deltagare som helst slår vilken deltagare som helst i [10] . Varje stark turnering är pancyklisk [11] och vertex pancyklisk [12] . Om en turnering är regelbunden (vilken deltagare som helst har samma antal vinster och förluster som andra deltagare), så är den också kant-pancyklisk [13] , men starka turneringar med fyra hörn kan inte vara kant-pancykliska.

Grafer med ett stort antal kanter

Mantels sats säger att varje oriktadvertexgraf som har åtminstonekanter och inte har flera kanter eller slingor antingen innehåller en triangel eller är en komplett tvådelad graf . Detta teorem kan förstärkas - vilken som helst oriktad Hamiltonsk graf med åtminstonekanter är antingen pancyklisk eller så är den [1] .

Det finns Hamilton-riktade grafer med hörn och bågar som inte är pancykliska, men alla Hamilton-riktade grafer med åtminstone bågar är pancykliska. Dessutom är en strikt sammankopplad vertexgraf där varje vertex har åtminstone grad (inkommande och utgående bågar räknas tillsammans) antingen pancyklisk eller är en komplett tvådelad graf [14] .

Grader av en graf

För vilken graf som helst definieras dess :e grad av grafen som en graf på samma uppsättning av hörn som har en kant mellan två avståndspunkter, vars avstånd inte överstiger . Om vertex 2-ansluten , så är enligt Fleischners sats en Hamiltonsk graf. Påståendet kan stärkas: grafen kommer nödvändigtvis att vara vertex-pancyklisk [15] . Mer strikt, om det är Hamiltonian, är det också pancyklisk [16] .

Beräkningskomplexitet

Att testa en graf för pancyklicitet är ett NP-komplett problem även för det speciella fallet med 3-kopplade kubiska grafer . Det är också ett NP-komplett problem att testa en graf för vertexpancyklicitet även för det speciella fallet med polyedriska grafer [17] . En NP-fullständig uppgift är också att testa kvadraten på en graf för Hamiltonianitet, och därmed också att testa för pancyklicitet [18] .

Historik

Pancyklicitet utforskades först av Harari och Moser i samband med turneringar [19] , såväl som av Muun [20] och Alpach [13] . Begreppet pancyklicitet namngavs av Bondi, som utökade konceptet för oriktade grafer [1] .

Anteckningar

  1. ↑ 1 2 3 4 5 Bondy, 1971 .
  2. ↑ 1 2 Randerath, Schiermeyer, Tewes, Volkmann, 2002 .
  3. ↑ Schmeichel, Mitchem, 1982 .
  4. ↑ Li, Corneil, Mendelsohn, 2000 , Proposition 2.5.
  5. ↑ Helden, 2007 , Corollary 3.78.
  6. ↑ Bernhart, Kainen, 1979 .
  7. ↑ Hakimi, Schmeichel, 1979 .
  8. ↑ Skowrońska, 1985 .
  9. ↑ Malkevitch, 1971 .
  10. ↑ Harary och Moser, 1966 , Corollary 5b.
  11. ↑ Harary och Moser, 1966 , sats 7.
  12. ↑ Moon, 1966 , sats 1.
  13. ↑ 12 Alspach , 1967 .
  14. ↑ Häggkvist, Thomassen, 1976 , sid. 20–40.
  15. ↑ Hobbs (1976) .
  16. ↑ Fleischner, 1976 .
  17. ↑ Li, Corneil, Mendelsohn, 2000 , satser 2.3 och 2.4.
  18. ↑ Underground (1978) .
  19. ↑ Harary, Moser, 1966 .
  20. ↑ Månen, 1966 .

Litteratur

Länkar