A panciklikus gráf olyan irányított vagy irányítatlan gráf , amely háromtól a gráfcsúcsok számáig minden lehetséges hosszúságú ciklust tartalmaz [1] . A panciklikus gráfok a Hamilton-gráfok általánosítása , olyan gráfok, amelyek ciklusai a lehető legnagyobb hosszúságúak.
Egy csúcsokkal rendelkező gráf panciklikus , ha bármely belüli gráf tartalmaz egy [1] hosszúságú ciklust . Egy gráf csúcs-panciklikus , ha bármely csúcsra és bármely ugyanazon határon belüli csúcsra a gráf tartalmaz egy csúcsot tartalmazó hosszúságú ciklust [2] . Hasonlóképpen, egy gráf élpanciklikus , ha bármely élre és bármely azonos határon belüli élre tartalmaz egy olyan hosszúságú ciklust, amely tartalmazza az élt [2] .
Egy kétrészes gráf nem lehet panciklikus, mert nem tartalmaz páratlan hosszúságú ciklusokat, de egy gráfot bipanciklikusnak mondunk , ha 4-től [3] -ig minden páros hosszúságú ciklust tartalmaz .
A maximális külső sík gráf egy olyan gráf, amelyet a síkban egy egyszerű sokszögből alakítunk ki, annak belsejét triagularizálva . Bármely maximális külső síkbeli gráf panciklikus, ami indukcióval mutatható ki. A gráf külső felülete egy n csúcsú ciklus, és ha a gráf többi részéhez csak egy éllel kapcsolt háromszöget ( a kettős háromszögelési gráfot alkotó fa levelével) töröljük, akkor egy maximális külső sík gráfot kapunk eggyel kevesebb számmal. csúcsokból, és az induktív feltevés szerint ennek a gráfnak az összes fennmaradó hosszúságú ciklusa van. Ha nagyobb figyelmet fordítunk az eltávolítandó háromszög kiválasztására, akkor ugyanezek az érvek azt a szigorúbb eredményt mutatják, hogy bármely maximális külső sík gráf csúcs-panciklikus [4] . Ugyanez igaz azokra a grafikonokra is, amelyek egy maximális külső síkbeli gráfot tartalmaznak feszítő részgráfként , különösen a kerekekre .
A maximális síkgráf olyan sík gráf, amelyben minden lap, beleértve a külsőt is, háromszög. Egy maximális síkgráf akkor és csak akkor csúcs-panciklikus, ha tartalmaz Hamilton-ciklust [5] – ha nem Hamilton-ciklus, akkor biztosan nem panciklikus, ha pedig Hamilton-gráf, akkor a Hamilton-ciklus belseje alkotja a külső felületet. a maximális külső sík gráf ugyanazon csúcsokon és éleken, amelyre az előző, külső síkbeli gráfok argumentumai alkalmazhatók [6] . Például az ábrán[ mi? ] mutatja az oktaéder gráf panciklicitását , egy hat csúcsú Hamilton-féle maximális síkgráfot. Pontosabban, ugyanezen okok miatt, ha egy maximális síkgráfnak van egy hosszúságú ciklusa , akkor minden kisebb hosszúságú ciklusa van [7] .
A Halin gráfok olyan síkgráfok, amelyeket egy fa síkbeli rajzából alakítanak ki, amelynek nincs második foka csúcsa, a fa leveleit összekötő ciklus hozzáadásával. A Halin-gráfok nem feltétlenül panciklikusak, de szinte panciklikusak abban az értelemben, hogy nincs legfeljebb egy hosszúságú ciklus. A hiányzó ciklus hossza szükségszerűen páros. Ha a Halin-gráf egyik belső csúcsának sincs három foka, akkor a gráf szükségszerűen panciklikus [8] .
1971-ben megállapították [1] , hogy a Hamilton-ciklus létezésének számos klasszikus feltétele is elegendő a panciklicitáshoz, ezért azt feltételezték, hogy bármely 4-kapcsolatú síkgráf panciklikus, de hamarosan találtak egy ellenpélda-családot . 9] .
A verseny egy irányított gráf, amelynek bármely csúcspárja között egy irányított ív található. Intuitív módon egy verseny felhasználható egy körmérkőzés szimulálására úgy, hogy a verseny minden egyes játékánál ívet rajzolunk a győztestől a vesztesig. Egy versenyt akkor és csak akkor nevezünk erősen összefüggőnek vagy egyszerűen erősnek, ha nem osztható két nem üres vesztesek és nyertesek részhalmazára, így bármelyik résztvevő legyőzi bármelyik résztvevőt a [10]-ben . Minden erős verseny panciklikus [11] és vertex panciklikus [12] . Ha egy verseny rendszeres (bármelyik résztvevőnek ugyanannyi győzelme és veresége van, mint a többi résztvevőnek), akkor az is élpanciklikus [13] , de a négy csúcsú erős versenyek nem lehetnek élpanciklikusak.
Mantel tétele kimondja, hogy minden irányítatlancsúcsgráf, amelynek legalábbélei vannak, és nincs több éle vagy hurokja, vagy tartalmaz háromszöget, vagy egy teljes kétrészes gráf . Ez a tétel megerősíthető - bármely irányítatlan Hamilton-gráf, amelynek legalábbélei vannak, vagy panciklikus, vagy [1] .
Vannak olyan Hamilton-irányított gráfok csúcsokkal és ívekkel, amelyek nem panciklikusak, de minden legalább ívet tartalmazó Hamilton-irányított gráf panciklikus. Ezenkívül egy szigorúan összefüggő csúcsgráf, amelyben minden csúcsnak van legalább foka (a bejövő és kimenő íveket együtt számolják), vagy panciklikus, vagy egy teljes bipartit gráf [14] .
Bármely gráf esetén a gráf edik fokát úgy definiáljuk, mint egy gráfot ugyanazon a csúcshalmazon, amelynek van egy éle bármely két csúcs között, amelyek közötti távolság in nem haladja meg a -t . Ha a 2-es csúcs kapcsolódik , akkor Fleischner tétele szerint egy Hamilton-gráf. Az állítás megerősíthető: a gráf szükségszerűen csúcs-panciklikus lesz [15] . Pontosabban, ha hamiltoni, akkor panciklikus is [16] .
Egy gráf panciklicitásának tesztelése NP-teljes probléma még a 3 összekapcsolt köbös gráfok speciális esetére is . Szintén NP-teljes probléma egy gráf csúcspanciklicitásának tesztelése még poliéder gráfok speciális esetére is [17] . Szintén egy NP-teljes feladat egy gráf négyzetének Hamiltonitás vizsgálata, és így a panciklicitás vizsgálata is [18] .
A panciklicitást először Harari és Moser tárta fel a versenyek [19] összefüggésében , valamint Muun [20] és Alpach [13] . A panciklicitás fogalmát Bondi nevezte el, aki kiterjesztette a fogalmat az irányítatlan gráfokra [1] .