Zobecněný Petersenův graf - Generalized Petersen graph

The Dürerův graf G(6, 2).

v teorie grafů, zobecněné Petersenovy grafy jsou rodina kubické grafy vytvořený spojením vrcholů a pravidelný mnohoúhelník k odpovídajícím vrcholům a hvězdný polygon. Zahrnují Petersenův graf a zobecnit jeden ze způsobů konstrukce Petersenova grafu. Zobecněná rodina grafů Petersen byla představena v roce 1950 H. S. M. Coxeter^[1] a dostal své jméno v roce 1969 Mark Watkins.^[2]

Definice a zápis

Ve Watkinsově notaci G(n, k) je graf se sadou vrcholů

${displaystyle {u_ {0}, u_ {1}, ldots, u_ {n-1}, v_ {0}, v_ {1}, ldots, v_ {n-1}}}$

a okrajová sada

${displaystyle {u_ {i} u_ {i + 1}, u_ {i} v_ {i}, v_ {i} v_ {i + k} | 0leq ileq n-1}}$

kde se indexy mají číst modulo n a k < n/ 2. Někteří autoři používají notaci GPG(n, k). Coxeterova notace pro stejný graf by byla {n} + {n/k}, kombinace Schläfliho symboly pro pravidelný n-gon a hvězdný polygon ze kterého je graf vytvořen. Samotný Petersenův graf je G(5, 2) nebo {5} + {5/2}.

Libovolný zobecněný Petersenův graf lze také sestrojit z a graf napětí se dvěma vrcholy, dvěma samostatnými smyčkami a jednou další hranou.^[3]

Příklady

Mezi zobecněné Petersenovy grafy patří n-hranol G(n, 1), Dürerův graf G(6, 2), Möbius-Kantorův graf G(8, 3) se dvanáctistěn G(10, 2), Desargues graf G(10, 3) a Nauru graf G(12, 5).

Čtyři zobecněné Petersenovy grafy - 3 hranol, 5 hranol, Dürerův graf a G(7, 2) - patří mezi sedm grafů, které jsou krychlový, 3-vrchol připojený, a dobře zakryté (což znamená, že všechny jejich maximální nezávislé množiny mít stejnou velikost).^[4]

Vlastnosti

Jeden ze tří Hamiltonovských cyklů v G(9, 2). Další dva Hamiltonovské cykly ve stejném grafu jsou symetrické při 40 ° rotaci výkresu.

Tato rodina grafů má řadu zajímavých vlastností. Například:

• G(n, k) je vrchol-tranzitivní (což znamená, že má symetrie, které převádějí jakýkoli vrchol na jakýkoli jiný vrchol), právě když (n, k) = (10, 2) nebo k² ≡ ± 1 (modn).

• G(n, k) je hrana tranzitivní (se symetrií, které berou jakoukoli hranu na jakoukoli jinou hranu) pouze v následujících sedmi případech:n, k) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5).^[5] Těchto sedm grafů je tedy jediných symetrický zobecněné Petersenovy grafy.

• G(n, k) je bipartitní kdyby a jen kdyby n je sudé a k je zvláštní.

• G(n, k) je Cayleyův graf kdyby a jen kdyby k² ≡ 1 (modn).

• G(n, k) je hypohamiltonián když n je shodný s 5 modulo 6 a k = 2, n - 2 nebo (n ± 1) / 2 (tyto čtyři možnosti k vést k izomorfním grafům). Je takéHamiltonian když n je dělitelné 4, alespoň 8, a k = n/ 2. Ve všech ostatních případech má Hamiltonovský cyklus.^[6] Když n odpovídá 3 modulo 6 G(n, 2) má přesně tři Hamiltonovské cykly.^[7] Pro G(n, 2), počet hamiltonovských cyklů lze vypočítat podle vzorce, který závisí na třídě shody n modulo 6 a zahrnuje Fibonacciho čísla.^[8]

• Každý zobecněný Petersenův graf je a graf jednotkové vzdálenosti.^[9]

Izomorfismy

G(n, k) je izomorfní s G(n, l) právě tehdy kl ≡ 1 (modn).^[10]

Obvod

Obvod G(n, k) je alespoň 3 a nejvýše 8, zejména:^[11]

${displaystyle g (G (n, k)) leq min vlevo {8, k + 3, {frac {n} {gcd (n, k)}} vpravo}.}$

Tabulka s přesnými hodnotami obvodu:

Stav	Obvod
${displaystyle n = 3k}$	3
${displaystyle n = 4k}$	4
${displaystyle k = 1}$
${displaystyle n = 5k}$	5
${displaystyle n = 5k / 2}$
${displaystyle k = 2}$
${displaystyle n = 6k}$	6
${displaystyle k = 3}$
${displaystyle n = 2k + 2}$
${displaystyle n = 7k}$	7
${displaystyle n = 7k / 2}$
${displaystyle n = 7k / 3}$
${displaystyle k = 4}$
${displaystyle n = 2k + 3}$
${displaystyle n = 3kpm 2}$
v opačném případě	8

Chromatické číslo a chromatický index

Bytost pravidelný, podle Brooksova věta jejich chromatické číslo nemohou být větší než jejich stupeň. Zobecněné Petersenovy grafy jsou kubické, takže jejich chromatický počet může být buď 2 nebo 3. Přesněji:

${displaystyle chi (G (n, k)) = {egin {cases} 2 & 2mid nland 2mid k 3 & 2mid nlor 2mid kend {cases}}}$

Kde ${displaystyle land}$ označuje logické A, zatímco ${displaystyle lor}$ logické NEBO. Například chromatický počet ${displaystyle G (5,2)}$ je 3.

• 

  3-zbarvení Petersenův graf nebo ${displaystyle G (5,2)}$

• 

  2-zbarvení Desargues graf nebo ${displaystyle G (10,3)}$

• 

  3-zbarvení Dürerův graf nebo ${displaystyle G (6,2)}$

Petersenův graf, přičemž pusť se, má chromatický index ze 4. Všechny ostatní zobecněné Petersenovy grafy mají chromatický index 3.^[12]

Zobecněný Petersenův graf G(9, 2) je jedním z mála grafů, o kterých je známo, že mají pouze jedno zbarvení 3 hran.^[13]

• 

  Čtyřbarevné zbarvení Petersenův graf nebo ${displaystyle G (5,2)}$

• 

  3barevné zbarvení Dürerův graf nebo ${displaystyle G (6,2)}$

• 

  3barevné zbarvení dvanáctistěn nebo ${displaystyle G (10,2)}$

• 

  3barevné zbarvení Desargues graf nebo ${displaystyle G (10,3)}$

• 

  3barevné zbarvení Nauru graf nebo ${displaystyle G (12,5)}$

Samotný Petersenův graf je jediný zobecněný Petersenův graf, který není 3barevný okraj.^[14]

Reference