Graficul de mers regulat

Un grafic de mers obișnuit este un grafic simplu în care numărul de mersuri închise de orice lungime de la un vârf la acesta nu depinde de alegerea vârfului.

Definiții echivalente

Să presupunem că este un grafic simplu. Să notăm matricea de adiacență a graficului , să notăm mulțimea de vârfuri ale graficului și să notăm polinomul caracteristic al subgrafului cu vârful eliminat . Următoarele afirmații sunt echivalente: $G$ $A$ $G$ $V(G)$ $G$ $\Phi _{Gv}(x)$ $Gv$ $v\in V(G).$

$G$ este un grafic de mers obișnuit.
$A^{k}$ este o matrice diagonală cu constantă diagonală pentru toate $k\geqslant 0.$
$\Phi _{Gu}(x)=\Phi _{Gv}(x)$ pentru toți $u,v\in V(G).$

Exemple

Graficele tranzitive de vârf sunt grafice obișnuite de mers.
Graficele semisimetrice sunt grafice obișnuite de mers.
Graficele distanței regulate sunt grafice regulate de mers.
Un grafic regulat conectat este un grafic de mers regulat dacă [1] .
- Are cel mult patru valori proprii distincte.
- Este lipsit de triunghiuri și are cel mult cinci valori proprii distincte.
- Este bipartit și are cel mult șase valori proprii distincte.

Proprietăți

Un grafic de mers obișnuit este neapărat regulat.
Complementul unui grafic de mers obișnuit este un grafic de mers obișnuit.
Produsul direct al graficelor obișnuite de mers este un grafic de mers obișnuit.
Produsul tensor al graficelor obișnuite de mers este un grafic de mers obișnuit.
Produsul puternic al graficelor obișnuite de mers este un grafic de mers obișnuit.
În general, un grafic obișnuit cu linii de mers nu este un grafic de mers obișnuit.

Note

↑ Farrell, Mark Distinct Eigenvalues și Walk-Regular Graphs - În căutarea structurii . Preluat: 21 iulie 2017. (nedefinit)

Link -uri

Chris Godsil, Brendan McKay, Condiții de fezabilitate pentru existența graficelor regulate de mers Arhivat la 7 februarie 2022 la Wayback Machine .