Önkomplementer gráf

Önkomplementer gráf: a kék „N” izomorf a komplementerével, a piros szaggatott vonallal rajzolt „Z”-vel.

A matematika, azon belül a gráfelmélet területén egy önkomplementer gráf (self-complementary graph, sc-graph) olyan gráf, ami izomorf a saját komplementerével. A legegyszerűbb nem triviális önkomplementer gráfok a 4 csúcsból álló útgráf és az 5 él hosszúságú körgráf.

Példák

Minden Paley-gráf önkomplementer. Például a 3 × 3-as bástyagráf (a 9 rendű Paley-gráf) önkomplementer, egy olyan szimmetriával, ami a középső csúcsot helyben hagyja, de felcseréli a rács négy sarkának és a négy oldal középpontjának a szerepét. Az erősen reguláris önkomplementer gráfok közül a 37-nél kevesebb csúcsúak mind Paley-gráfok; 37, 41 és 49 csúccsal azonban léteznek olyan erősen reguláris gráfok, melyek nem Paley-gráfok. A Rado-gráf egy végtelen, önkomplementer gráf.

Tulajdonságok

Egy n-csúcsú önkomplementer véges gráf éleinek száma pontosan fele az azonos csúcsszámú teljes gráfénak, tehát n(n − 1)/4 éle van, és (ha egynél több csúcsa), akkor átmérője vagy 2, vagy 3. Mivel n(n −1)-nek oszthatónak kell lennie 4-gyel, n-nek kongruensnek kell lennie 0-val vagy 1-gyel modulo 4; így például egy 6 csúcsú gráf nem lehet önkomplementer.

Minden önkomplementer gráf összefüggő, továbbá Hamilton-utat tartalmaz.

Egy $n>5$ csúcsú önkomplementer gráf tartalmaz $l$ hosszúságú kört bármely $3\le l\le n-2$ értékre; ebből következően az ilyen méretű önkomplementer gráfok kerülete vagy $n$, és akkor a gráfnak van Hamilton-köre, vagy $n-1$, vagy $n-2$.

Bármely $c$ konstans esetén csak véges számú olyan önkomplementer gráf létezik, melynek génusza $g(G)\le c$, illetve vastagsága $t(G)\le c$. Specifikusan, a legalább 9 csúcsú önkomplementer gráfok nem síkba rajzolhatók.

Az önkomplementer gráfok kromatikus számára a következő összefüggés igazolható: $\sqrt{n}\le \chi (G)\le \frac{n+1}{2}.$
Továbbá bármely konstans $r$-re csak véges sok $r$-részes ($r$ kromatikus számú) gráf található (de legalább egy mindig).

Számítási bonyolultság

Annak a problémája, hogy két önkomplementer gráf egymással izomorf-e, illetve hogy adott gráf önkomplementer-e az általánosabb gráfizomorfizmus-problémával polinom-ekvivalens. Polinom időben eldönthető, hogy egy önkomplementer gráfnak van-e Hamilton-köre.

Fordítás

• Sablon:Fordítás

További információk

• Sablon:Mathworld
• Sablon:OEIS, az adott csúcsú önkomplementer gráfok számának sorozata