Önkomplementer gráf

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.

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

Példák

Minden Paley-gráf önkomplementer.^[1] 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.^[2] 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.^[3] 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.^[1] 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.^[4][5][6]

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

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

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

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.^[7] Polinom időben eldönthető, hogy egy önkomplementer gráfnak van-e Hamilton-köre.

Fordítás

• Ez a szócikk részben vagy egészben a Self-complementary graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.