Ö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ákSzerkesztés

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ágokSzerkesztés

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   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  .[6]

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.[6]

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).[6]

Számítási bonyolultságSzerkesztés

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ásSzerkeszté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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. a b Sachs, Horst (1962), "Über selbstkomplementäre Graphen", Publicationes Mathematicae Debrecen 9: 270–288.
  2. Shpectorov, S. (1998), "Complementary l1-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.
  4. Clapham, C. R. J. "Hamiltonian Arcs in Self-Complementary Graphs." Disc. Math. 8, 251-255, 1974.
  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.
  6. 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 .
  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.

További információkSzerkesztés