Ö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.

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 $n>5$ csúcsú önkomplementer gráf tartalmaz $l$ hosszúságú kört bármely $3\leq l\leq 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$ .^[6]

Bármely $c$ konstans esetén csak véges számú olyan önkomplementer gráf létezik, melynek génusza $g(G)\leq c$ , illetve vastagsága $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ó: ${\sqrt {n}}\leq \chi (G)\leq {\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).^[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.

Jegyzetek

↑ ^a ^b Sachs, Horst (1962), "Über selbstkomplementäre Graphen", Publicationes Mathematicae Debrecen 9: 270–288.
↑ Shpectorov, S. (1998), "Complementary l₁-graphs", Discrete Mathematics 192 (1-3): 323–331, DOI 10.1016/S0012-365X(98)0007X-1.
↑ Rosenberg, I. G. (1982), "Regular and strongly regular selfcomplementary graphs", Theory and practice of combinatorics, vol. 60, North-Holland Math. Stud., Amsterdam: North-Holland, pp. 223–238.
↑ Clapham, C. R. J. "Hamiltonian Arcs in Self-Complementary Graphs." Disc. Math. 8, 251-255, 1974.
↑ Camion, P. "Hamiltonian Chains in Self-Complementary Graphs." In Colloque sur la théorie des graphes (Paris, 1974) (Ed. P. P. Gillis and S. Huyberechts). Cahiers du Centre Études de Recherche Opér. (Bruxelles) 17, pp. 173-183, 1975.
↑ ^a ^b ^c ^d Farrugia, A. "Self-Complementary Graphs and Generalisations: a Comprehensive Reference Manual." Aug. 1999. http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf .
↑ Colbourn, Marlene J. & Colbourn, Charles J. (1978), "Graph isomorphism and self-complementary graphs", SIGACT News 10 (1): 25–29, DOI 10.1145/1008605.1008608.

További információk

Weisstein, Eric W.: Self-Complementary Graph (angol nyelven). Wolfram MathWorld
(A000171 sorozat az OEIS-ben), az adott csúcsú önkomplementer gráfok számának sorozata

Matematikaportál • összefoglaló, színes tartalomajánló lap

[sachs-1] Sachs, Horst (1962), "Über selbstkomplementäre Graphen", Publicationes Mathematicae Debrecen 9: 270–288.

[2] Shpectorov, S. (1998), "Complementary l₁-graphs", Discrete Mathematics 192 (1-3): 323–331, DOI 10.1016/S0012-365X(98)0007X-1.

[3] Rosenberg, I. G. (1982), "Regular and strongly regular selfcomplementary graphs", Theory and practice of combinatorics, vol. 60, North-Holland Math. Stud., Amsterdam: North-Holland, pp. 223–238.

[Clapham1974-4] Clapham, C. R. J. "Hamiltonian Arcs in Self-Complementary Graphs." Disc. Math. 8, 251-255, 1974.

[Camion1975-5] Camion, P. "Hamiltonian Chains in Self-Complementary Graphs." In Colloque sur la théorie des graphes (Paris, 1974) (Ed. P. P. Gillis and S. Huyberechts). Cahiers du Centre Études de Recherche Opér. (Bruxelles) 17, pp. 173-183, 1975.

[Farrugia1999-6] Farrugia, A. "Self-Complementary Graphs and Generalisations: a Comprehensive Reference Manual." Aug. 1999. http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf .

[7] Colbourn, Marlene J. & Colbourn, Charles J. (1978), "Graph isomorphism and self-complementary graphs", SIGACT News 10 (1): 25–29, DOI 10.1145/1008605.1008608.

[1]

[2]

[3]

[4]

[5]

[6]

[7]