Procházkový pravidelný graf - Walk-regular graph - Wikipedia

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"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Říjen 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

tento článek případně obsahuje původní výzkum. Prosím zlepšit to podle ověřování vznesené nároky a přidání vložené citace. Výroky sestávající pouze z původního výzkumu by měly být odstraněny. (Říjen 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

V diskrétní matematice, a běžný graf je jednoduchý graf kde počet uzavřených chodů libovolné délky od vrcholu k sobě nezávisí na výběru vrcholu.

Ekvivalentní definice

Předpokládejme to ${ displaystyle G}$ je jednoduchý graf. Nechat ${ displaystyle A}$ označit matici sousedství ${ displaystyle G}$, ${ displaystyle V (G)}$ označuje množinu vrcholů ${ displaystyle G}$, a ${ displaystyle Phi _ {G-v} (x)}$ označuje charakteristický polynom subgrafu s odstraněnými vrcholy ${ displaystyle G-v}$ pro všechny ${ displaystyle v v V (G).}$Pak jsou ekvivalentní následující:

• ${ displaystyle G}$ je pravidelná chůze.
• ${ displaystyle A ^ {k}}$ je matice s konstantní úhlopříčkou pro všechny ${ displaystyle k geq 0.}$
• ${ displaystyle Phi _ {G-u} (x) = Phi _ {G-v} (x)}$ pro všechny ${ displaystyle u, v ve V (G).}$

Příklady

• The vertex-tranzitivní grafy chodí pravidelně.
• The polosymetrické grafy chodí pravidelně.^{[1][nespolehlivý zdroj ]}
• The vzdálenost-pravidelné grafy chodí pravidelně. Obecněji řečeno, jakýkoli jednoduchý homogenní graf koherentní algebra je pravidelná chůze.
• Připojeno běžný graf je pravidelná chůze, pokud:^{[pochybný – diskutovat][Citace je zapotřebí ]}
  • Má nejvýše čtyři odlišné vlastní hodnoty.
  • to je bez trojúhelníků a má nejvýše pět odlišných vlastních čísel.
  • to je bipartitní a má nejvýše šest odlišných vlastních čísel.

Vlastnosti

• Pravidelný graf je nezbytně běžný graf.
• Doplňky procházkových pravidelných grafů je pravidelných procházek.
• Kartézské výrobky procházkových pravidelných grafů je pravidelných procházek.
• Kategorie produktů procházkových pravidelných grafů je pravidelných procházek.
• Silné produkty procházkových pravidelných grafů je pravidelných procházek.
• Obecně platí, že hranový graf grafu pravidelná chůze není pravidelná chůze.

Reference

externí odkazy

• Chris Godsil a Brendan McKay, Podmínky proveditelnosti pro existenci průběžných grafů.