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.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.Farrugia, A. "Self-Complementary Graphs and Generalisations: a Comprehensive Reference Manual." Aug. 1999. http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf .
Egy csúcsú önkomplementer gráf tartalmaz hosszúságú kört bármely értékre; ebből következően az ilyen méretű önkomplementer gráfok kerülete vagy , és akkor a gráfnak van Hamilton-köre, vagy , vagy .
Bármely konstans esetén csak véges számú olyan önkomplementer gráf létezik, melynek génusza , illetve vastagsága . 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ó: Továbbá bármely konstans -re csak véges sok -részes ( 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
Jegyzetek
További információk
, az adott csúcsú önkomplementer gráfok számának sorozata
Kategória:Gráfcsaládok