Schläfliho graf - Schläfli graph

Schläfliho graf
Schläfli graph.svg
Vrcholy27
Hrany216
Poloměr2
Průměr2
Obvod3
Automorfismy51840
Chromatické číslo9
VlastnostiSilně pravidelné
Bez drápů
Hamiltonian
Tabulka grafů a parametrů

V matematický pole teorie grafů, Schläfliho graf, pojmenoval podle Ludwig Schläfli, je 16-pravidelný neorientovaný graf s 27 vrcholy a 216 hranami. Je to silně pravidelný graf s parametry srg (27, 16, 10, 8).

Konstrukce

Schläfliho graf je považován za 1-kostru 221 polytop. Tato symetrická projekce obsahuje 2 kroužky o 12 vrcholech a 3 vrcholy shodující se ve středu.

The průsečíkový graf z 27 řádků na a kubický povrch je lokálně lineární graf toto je doplněk Schläfliho grafu. To znamená, že v Schläfliho grafu sousedí dva vrcholy právě tehdy, pokud tomu tak je překroutit.[1]

Schläfliho graf může být také sestrojen ze systému osmrozměrných vektorů

(1, 0, 0, 0, 0, 0, 1, 0),
(1, 0, 0, 0, 0, 0, 0, 1) a
(−1/2, −1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2),

a dalších 24 vektorů získaných permutací prvních šesti souřadnic těchto tří vektorů. Těchto 27 vektorů odpovídá vrcholům Schläfliho grafu; dva vrcholy sousedí právě tehdy, mají-li odpovídající dva vektory 1 vnitřní produkt.[2]

Alternativně lze tento graf považovat za doplněk grafu kolinearity grafu zobecněný čtyřúhelník GQ (2, 4).

Podgrafy a sousedství

The sousedství libovolného vrcholu v Schläfliho grafu tvoří 16grafový podgraf, ve kterém má každý vrchol 10 sousedů (čísla 16 a 10 vycházející z parametrů Schläfliho grafu jako silně pravidelný graf). Tyto podgrafy jsou všechny izomorfní do doplňkový graf z Clebschův graf.[1][3] Protože Clebschův graf je bez trojúhelníků, Schläfliho graf je bez drápů. Hraje důležitou roli v teorii struktury grafů bez drápů od Chudnovsky & Seymour (2005).

Jakékoli dvě šikmé čáry z těchto 27 patří k jedinečnému Schläfli dvojitá šestka konfigurace, sada 12 řádků, jejichž průsečíkový graf je a korunový graf ve kterém mají dva řádky disjunktní sousedství. Odpovídajícím způsobem, v Schläfliho grafu, každá hrana uv patří jednoznačně k podgrafu v podobě a kartézský součin z kompletní grafy K.6 K.2 takovým způsobem, že u a proti patří k různým K.6 podgrafy produktu. Schläfliho graf má celkem 36 podgrafů této formy, z nichž jeden se skládá z vektorů nuly v osmi-dimenzionální reprezentaci popsané výše.[2]

Ultrahomogenita

Graf je definován jako k- vícehomogenní pokud každý izomorfismus mezi dvěma z nich indukované podgrafy maximálně k vrcholy lze rozšířit na automorfismus celého grafu. Pokud je graf 5-ultrahomogenní, je ultrahomogenní pro všechny k; jediný konečný připojeno grafy tohoto typu jsou kompletní grafy, Turánovy grafy, 3 × 3 věže grafy acyklus. Nekonečný Rado graf je spočetně ultrahomogenní. Existují pouze dva spojené grafy, které jsou 4-ultrahomogenní, ale ne 5-ultrahomogenní: Schläfliho graf a jeho doplněk. Důkaz se opírá o klasifikace konečných jednoduchých skupin.[4]

Viz také

  • Gossetův graf - obsahuje Schläfliho graf jako indukovaný podgraf sousedství jakéhokoli vrcholu.

Poznámky

  1. ^ A b Holton & Sheehan (1993).
  2. ^ A b Bussemaker & Neumaier (1992).
  3. ^ Cameron & van Lint (1991). Všimněte si, že Cameron a van Lint používají alternativní definici těchto grafů, ve kterých jsou Schläfliho i Clebschův graf doplněno z jejich definic zde.
  4. ^ Buczak (1980); Cameron (1980); Devillers (2002).

Reference

  • Buczak, J. M. J. (1980), Teorie konečné skupiny, Ph.D. práce, Oxford University. Jak uvádí Devillers (2002).
  • Bussemaker, F. C .; Neumaier, A. (1992), „Výjimečné grafy s nejmenší vlastní hodnotou-2 a souvisejícími problémy“, Matematika výpočtu, 59 (200): 583–608, doi:10.1090 / S0025-5718-1992-1134718-6.
  • Cameron, Peter Jephson (1980), „6-tranzitivní grafy“, Journal of Combinatorial Theory, Series B, 28 (2): 168–179, doi:10.1016/0095-8956(80)90063-5. Jak uvádí Devillers (2002).
  • Cameron, Peter Jephson; van Lint, Jacobus Hendricus (1991), Vzory, grafy, kódy a jejich odkazy, Studentské texty London Mathematical Society, 22, Cambridge University Press, str. 35, ISBN  978-0-521-41325-1.
  • Chudnovský, Maria; Seymour, Paule (2005), „Struktura grafů bez drápů“, Průzkumy v kombinatorice 2005 (PDF), London Math. Soc. Přednáška Ser., 327, Cambridge: Cambridge Univ. Press, str. 153–171, PAN  2187738.
  • Devillers, Alice (2002), Klasifikace některých homogenních a ultrahomogenních struktur, Ph.D. práce, Université Libre de Bruxelles.
  • Holton, D. A .; Sheehan, J. (1993), Petersenův graf, Cambridge University Press, s. 270–271.

externí odkazy