Kendini tamamlayan grafik - Self-complementary graph

Kendini tamamlayan bir grafik: Mavi N, tamamlayıcısı olan kesikli kırmızı Z'ye izomorftur.

Bir kendini tamamlayan grafik bir grafik hangisi izomorf onun için Tamamlayıcı. En basit, önemsiz olmayan kendi kendini tamamlayan grafikler 4 köşeli yol grafiği ve 5 köşe döngü grafiği.

Örnekler

Her Paley grafiği kendini tamamlayıcıdır.[1] Örneğin, 3 × 3 kalenin grafiği (Dokuzuncu derecenin Paley grafiği) merkez tepe noktasını yerinde tutan ancak ızgaranın dört kenar orta noktası ve dört köşesinin rollerini değiştiren bir simetri ile kendi kendini tamamlar.[2] Herşey kesinlikle düzenli 37'den az köşeli kendi kendini tamamlayan grafikler Paley grafikleridir; ancak, 37, 41 ve 49 köşelerde, Paley grafikleri olmayan son derece düzenli grafikler vardır.[3]

Rado grafiği sonsuz kendi kendini tamamlayan bir grafiktir.[4]

Özellikleri

Bir n-vertex kendi kendini tamamlayan grafiğin tam olarak yarı sayıda kenarı vardır. tam grafik yani n(n - 1) / 4 kenar ve (birden fazla köşe varsa) olması gerekir çap ya 2 ya da 3.[1] Dan beri n(n −1) 4 ile bölünebilir olmalıdır, n olmalıdır uyumlu 0 veya 1 mod 4'e; örneğin, 6 köşeli bir grafik kendi kendini tamamlayıcı olamaz.

Hesaplama karmaşıklığı

Kendini tamamlayan iki grafiğin izomorf olup olmadığını kontrol etme ve verilen bir grafiğin kendi kendini tamamlayıcı olup olmadığını kontrol etme sorunları şunlardır: polinom-zaman eşdeğeri generale grafik izomorfizm problemi.[5]

Referanslar

  1. ^ a b Sachs, Horst (1962), "Über selbstkomplementäre Graphen", Mathematicae Debrecen Yayınları, 9: 270–288, BAY  0151953.
  2. ^ Shpectorov, S. (1998), "Tamamlayıcı l1-graflar ", Ayrık Matematik, 192 (1–3): 323–331, doi:10.1016 / S0012-365X (98) 0007X-1, BAY  1656740.
  3. ^ Rosenberg, I. G. (1982), "Düzenli ve son derece düzenli kendi kendini tamamlayan grafikler", Kombinasyon teorisi ve pratiği, North-Holland Math. Damızlık., 60, Amsterdam: North-Holland, s. 223–238, BAY  0806985.
  4. ^ Cameron, Peter J. (1997), "Rastgele grafik", Paul Erdős'ün matematiği, II, Algorithms Combin., 14, Berlin: Springer, s. 333–351, arXiv:1301.7544, Bibcode:2013arXiv1301.7544C, BAY  1425227. Özellikle bkz. Önerme 5.
  5. ^ Colbourn, Marlene J .; Colbourn, Charles J. (1978), "Grafik izomorfizmi ve kendi kendini tamamlayan grafikler", SIGACT Haberleri, 10 (1): 25–29, doi:10.1145/1008605.1008608.

Dış bağlantılar