Vzdálenost-pravidelný graf - Distance-regular graph

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Pravidelný graf vzdálenosti"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Červen 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika, a vzdálenost-pravidelný graf je pravidelný graf tak, že pro libovolné dva vrcholy proti a w, počet vrcholů na vzdálenost j z proti a na dálku k z w záleží jen na j, k, a i = d (v, w).

Každý vzdálenost-tranzitivní graf je pravidelná vzdálenost. Ve skutečnosti byly vzdálenosti-pravidelné grafy zavedeny jako kombinatorické zobecnění vzdáleně přechodných grafů, které mají numerické vlastnosti pravidelnosti těchto grafů, aniž by nutně měly velkou automorfická skupina.

Křižovatková pole

Ukázalo se, že graf ${displaystyle G}$ průměru ${displaystyle d}$ is distance-regular if and only if there is a array of integers ${displaystyle {b_ {0}, b_ {1}, ldots, b_ {d-1}; c_ {1}, ldots, c_ {d}}}$ takové, že pro všechny ${displaystyle 1leq jleq d}$, ${displaystyle b_ {j}}$ udává počet sousedů ${displaystyle u}$ na dálku ${displaystyle j + 1}$ z ${displaystyle v}$ a ${displaystyle c_ {j}}$ udává počet sousedů ${displaystyle u}$ na dálku ${displaystyle j-1}$ z ${displaystyle v}$ pro jakýkoli pár vrcholů ${displaystyle u}$ a ${displaystyle v}$ na dálku ${displaystyle j}$ na ${displaystyle G}$. Pole celých čísel charakterizujících pravidelný graf vzdálenosti je známé jako jeho průnikové pole.

Cospectral distance-regular graphs

Dvojice propojených pravidelných grafů vzdálenosti jsou cospectral právě když mají stejné průnikové pole.

Pravidelný graf vzdálenosti je odpojen, pouze pokud je a disjunktní unie cospectral distance-regular graphs.

Vlastnosti

Předpokládat ${displaystyle G}$ je spojitý pravidelný graf vzdálenosti mocenství ${displaystyle k}$ s průnikovým polem ${displaystyle {b_ {0}, b_ {1}, ldots, b_ {d-1}; c_ {1}, ldots, c_ {d}}}$. Pro všechny ${displaystyle 0leq jleq d}$: nechte ${displaystyle G_ {j}}$ označit ${displaystyle k_ {j}}$-pravidelný graf s matice sousedství ${displaystyle A_ {j}}$ vytvořený vztahem dvojic vrcholů na ${displaystyle G}$ na dálku ${displaystyle j}$a nechte ${displaystyle a_ {j}}$ označit počet sousedů ${displaystyle u}$ na dálku ${displaystyle j}$ z ${displaystyle v}$ pro jakýkoli pár vrcholů ${displaystyle u}$ a ${displaystyle v}$ na dálku ${displaystyle j}$ na ${displaystyle G}$.

Graficko-teoretické vlastnosti

• ${displaystyle {frac {k_ {j + 1}} {k_ {j}}} = {frac {b_ {j}} {c_ {j + 1}}}}$ pro všechny ${displaystyle 0leq j$.
• ${displaystyle b_ {0}> b_ {1} geq cdots geq b_ {d-1}> 0}$ a ${displaystyle 1 = c_ {1} leq cdots leq c_ {d} leq b_ {0}}$.

Spektrální vlastnosti

• ${displaystyle kleq {frac {1} {2}} (m-1) (m + 2)}$ pro libovolnou multiplicitu vlastních čísel ${displaystyle m> 1}$ z ${displaystyle G}$, pokud ${displaystyle G}$ je kompletní multipartitní graf.
• ${displaystyle dleq 3m-4}$ pro libovolnou multiplicitu vlastních čísel ${displaystyle m> 1}$ z ${displaystyle G}$, pokud ${displaystyle G}$ je cyklický graf nebo úplný multipartitní graf.
• ${displaystyle lambda v {pm k}}$ -li ${displaystyle lambda}$ je jednoduchá vlastní hodnota ${displaystyle G}$.
• ${displaystyle G}$ má ${displaystyle d + 1}$ odlišné vlastní hodnoty.

Li ${displaystyle G}$ je velmi pravidelné, pak ${displaystyle nleq 4m-1}$ a ${displaystyle kleq 2m-1}$.

Příklady

Některé první příklady pravidelných grafů vzdálenosti zahrnují:

• The kompletní grafy.
• The cyklické grafy.
• The liché grafy.
• The Mooreovy grafy.
• Kolinearitní graf a pravidelné blízko mnohoúhelníku.
• The Wellsův graf a Sylvesterův graf.
• Silně pravidelné grafy průměru ${displaystyle 2}$.

Klasifikace pravidelných grafů vzdálenosti

Existuje jen konečně mnoho odlišných spojitých grafů vzdálenosti a pravidel jakékoli dané valence ${displaystyle k> 2}$.^[1]

Podobně existuje jen konečně mnoho odlišných spojitých pravidelných grafů vzdálenosti s libovolnou danou multiplicitou vlastních čísel ${displaystyle m> 2}$^[2] (s výjimkou úplných vícedílných grafů).

Kubické vzdálenosti - pravidelné grafy

The krychlový vzdálenostně pravidelné grafy byly kompletně klasifikovány.

13 odlišných kubických pravidelných grafů je K.₄ (nebo čtyřstěn ), K._3,3, Petersenův graf, krychle, Heawoodův graf, Pappusův graf, Coxeterův graf, Tutte – Coxeterův graf, dvanáctistěn, Desargues graf, Tutte 12-klec, Biggs – Smithův graf a Pěstounský graf.

Reference

Další čtení

• Godsil, C. D. (1993). Algebraická kombinatorika. Chapman and Hall Mathematics Series. New York: Chapman a Hall. str. xvi + 362. ISBN  978-0-412-04131-0. PAN  1220704.CS1 maint: ref = harv (odkaz)