Vanlig promenadgraf

En vanlig gånggraf är en enkel graf där antalet slutna promenader oavsett längd från en vertex till den inte beror på valet av vertex.

Motsvarande definitioner

Låt oss anta att det är en enkel graf. Låt beteckna grafens närliggande matris , beteckna uppsättningen av hörn i grafen , och beteckna det karakteristiska polynomet för subgrafen med den borttagna vertexen. Följande påståenden är ekvivalenta: $G$ $A$ $G$ $V(G)$ $G$ $\Phi _{Gv}(x)$ $Gv$ $v\in V(G).$

$G$ är en vanlig gånggraf.
$A^{k}$ är en diagonal matris med diagonalkonstant för alla $k\geqslant 0.$
$\Phi _{Gu}(x)=\Phi _{Gv}(x)$ för alla $u,v\in V(G).$

Exempel

Vertex-transitiva grafer är vanliga gånggrafer.
Semisymmetriska grafer är vanliga gånggrafer.
Avstånd-reguljära grafer är vanliga gånggrafer.
En ansluten vanlig graf är en vanlig gånggraf om [1] .
- Den har högst fyra distinkta egenvärden.
- Den är fri från trianglar och har högst fem distinkta egenvärden.
- Den är tvådelad och har högst sex distinkta egenvärden.

Egenskaper

En vanlig promenadgraf är nödvändigtvis regelbunden.
Komplementet till en vanlig gånggraf är en vanlig gånggraf.
Den direkta produkten av vanliga gångdiagram är en vanlig gånggraf.
Tensorprodukten av vanliga gånggrafer är en vanlig gånggraf.
Den starka produkten av vanliga gånggrafer är en vanlig gånggraf.
I allmänhet är en vanlig gånglinjegraf inte en vanlig gånggraf.

Anteckningar

↑ Farrell, Mark Distinct Eigenvärden och Walk-Regular Graphs - In Search of Structure . Hämtad: 21 juli 2017. (obestämd)

Länkar

Chris Godsil, Brendan McKay, Genomförbarhetsvillkor för förekomsten av gång-reguljära grafer Arkiverad 7 februari 2022 på Wayback Machine .