Split gráf

A matematika, azon belül a gráfelmélet területén egy split gráf, hasított gráf vagy kettéhasadó gráf (split graph) olyan gráf, melynek csúcsai egy klikkbe (teljes részgráfba) és egy független csúcshalmazba particionálhatók. Elsőként Földes and Hammer (1977a, 1977b) tanulmányozta őket, tőlük függetlenül Tyshkevich and Chernyak (1979) is bevezette a fogalmat.^[1]

Egy split gráf, klikkbe és független csúcshalmazba particionálva.

Egy split gráfnak lehet egynél több lehetséges klikkre és független halmazra való particionálása is; például az a–b–c útgráf egy split gráf, melynek csúcsai háromféleképpen particionálhatók:

1. az {a,b} klikk és a {c}
2. a {b,c} klikk és az {a} független halmaz
3. a {b} klikk és az {a,c} független halmaz

A split gráfok tiltott részgráfjaik alapján jellemezhetők: egy gráf pontosan akkor split gráf, ha egyetlen feszített részgráfja sem 4 vagy 5 csúcsú kör, vagy diszjunkt élpár (ami a 4-kör komplementere).^[2]

Más gráfcsaládokkal való kapcsolata

A definíció alapján a split gráfok nyilvánvalóan zártak a komplementerképzés műveletére nézve.^[3] Egy másik karakterizáció szerint a split gráfok azok a merev körű gráfok, melyek komplementere is merev körű.^[4] Ahogy a merev körű gráfok a fák al-fáinak metszetgráfjai, ugyanígy a split gráfok csillaggráfok al-csillagjainak metszetgráfjai.^[5] Csaknem minden merev körű gráf splitgráf; ahogy n tart végtelenhez, az n-csúcsú merev körű gráfok között a split gráfok aránya egyhez tart.^[6]

Mivel a merev körű gráfok perfektek, ezért a split gráfok is azok. A dupla split gráfok^[7] családjának tagjait split gráfokból lehet előállítani minden csúcs megduplázásával (így a klikk antipárosítást feszít ki, a független csúcshalmaz pedig párosítást); a dupla split gráfok a perfekt gráfok öt alaposztályának egyike, melyekből az összes többi perfekt gráf előállítható, ahogy az megjelenik (Chudnovsky et al. 2006) erős perfektgráf-tétel-bizonyításában.

Ha egy gráf egyszerre split és intervallumgráf, akkor komplementere egyszerre split és összehasonlíthatósági gráf, ugyanez igaz megfordítva. A split összehasonlíthatósági gráfok és így a split intervallumgráfok ezért jellemezhetőek három tiltott feszített részgráfjukkal.^[8] A split kográfok pontosan megegyeznek a küszöbgráfokkal, a split permutációgráfok pedig pontosan azok az intervallumgráfok, melyek komplementerei is intervallumgráfok.^[9] A split gráfok komplementer kromatikus száma 2.

Algoritmikus problémák

Tekintsük a G split gráfot, melynek létezik egy C klikkbe és I független csúcshalmazba particionálása. Ekkor a split gráf minden maximális klikkje vagy C-vel egyezik meg, vagy egy I-beli csúcs szomszédságával. Ezért a split gráfokban könnyű feladat meghatározni a maximális klikket, illetve komplementer feladatként a maximális független halmazt. Tetszőleges split gráfban a következő három lehetőség valamelyikének igaznak kell lennie:^[10]

1. Létezik olyan x csúcs I-ben, hogy C ∪ {x} teljes. Ebben az esetben C ∪ {x} egy maximális klikk, I pedig maximális független halmaz.
2. Létezik x csúcs C-ben, hogy I ∪ {x} független. Ebben az esetben I ∪ {x} maximális független halmaz és C maximális klikk.
3. C maximális klikk és I maximális független halmaz. Ebben az esetben G-nek a (C,I) klikkre és független halmazra felbontása egyedi, C a maximális klikk és I a maximális független halmaz.

Néhány optimalizálási probléma, ami általánosabb gráfcsaládokon NP-teljes – köztük a gráfszínezés – hasonlóan egyszerűsödik split gráfokat tekintve. A Hamilton-kör keresése továbbra is NP-teljes, még olyan split gráfokra is, melyek erősen merev körűek.^[11] Ismert továbbá, hogy a minimális domináló csúcshalmaz problémája split gráfokra is NP-teljes.^[12]

Fokszámsorozatok

A split gráfok figyelemre méltó sajátossága, hogy pusztán a gráf fokszámsorozata alapján felismerhetők. Legyen a G gráf fokszámsorozata d₁ ≥ d₂ ≥ ... ≥ d_n, és m a legnagyobb i érték, amire d_i ≥ i − 1. Ekkor G pontosan akkor split gráf, ha

${\displaystyle \sum _{i=1}^{m}d_{i}=m(m-1)+\sum _{i=m+1}^{n}d_{i}.}$

Ha ez az eset áll fenn, akkor a legnagyobb fokszámú m csúcs maximális klikket alkot G-ben, a maradék csúcsok pedig független csúcshalmazt.^[13]

Split gráfok leszámlálása

(Royle 2000) megmutatta, hogy az n-csúcsú split gráfok és bizonyos Sperner-rendszerek között bijekció létesíthető. Ezt a tényt kihasználva meghatározta az n csúcsú (nem izomorf) split gráfok számát. Kis n értékekre, n = 1-től kezdve, ezek:

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (A048194 sorozat az OEIS-ben).

Ezt a gráfleszámlálási eredményt korábban (Tyshkevich & Chernyak 1990) is bizonyította.