Graphs with the same CDC on 8 Vertices

• ← Walks and CDCs
• Home

Here we give an exhaustive list of all 32 pairs of non-isomorphic graphs on 8 vertices which have the same CDC. This automatically includes those graphs on ⩽ 8 vertices since any \(n\leqslant8\) vertex pair of graphs \(G\), \(H\) with the same CDC will appear here as the pair \(G+(8-n)K_1\), \(H+(8-n)K_1\). For relevant definitions, please refer to my undergraduate dissertation, or my recent publication with Irene Sciriha.

The numbering of the graphs here is in accordance with the graph data on Brendan McKay's webpage. The colouring of the vertices (and walk matrix rows) is so that vertices of the same colour have the same number of \(k\)-walks, for any value of \(k\).

It's easy to work with these graphs in Mathematica by importing them from McKay's webpage; the pairs of numbers are available as CSV files from the root directory of this site in the form cdcX.csv. (X here stands for the number of vertices; the graphs pairs on this webpage correspond to those in cdc8.csv). For instance:

Click on code to copy to clipboard

I have also computed the pairs for X=6, 7 and 9, you can see more about those here. Notice that I am making use of the Walks package above.

Ryser Switches

A Ryser switch is a degree-sequence preserving operation on a pair of edges in a given graph. In the list below, it turns out that all but one pair of graphs is the result of a single Ryser switch. (The exceptional pair (5358, 11716) requires two).

Given a graph \(G\) and edges \(uv, xy\in E(G)\) such that \(ux, vy\notin E(G)\), the Ryser switch on the edges \(uv\) and \(xy\) replaces those edges with \(ux\) and \(vy\). We denote the graph obtained by \(\operatorname{ryser}(G,uv,xy)\).

Pair (447, 958)

Graph 447

Graph 958

\(\begin{pmatrix} \color{red}1&\color{red}2\\ \color{red}1&\color{red}2\\ \color{red}1&\color{red}2\\ \color{blue}1&\color{blue}0\\ \color{blue}1&\color{blue}0\\ \color{red}1&\color{red}2\\ \color{red}1&\color{red}2\\ \color{red}1&\color{red}2 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{958}=\operatorname{ryser}(G_{447},16, 38)\)

Pair (1030, 1162)

Graph 1030

Graph 1162

\(\begin{pmatrix} \color{red}1&\color{red}2&\color{red}5\\ \color{red}1&\color{red}2&\color{red}5\\ \color{blue}1&\color{blue}1&\color{blue}3\\ \color{blue}1&\color{blue}1&\color{blue}3\\ \color{red}1&\color{red}2&\color{red}5\\ \color{red}1&\color{red}2&\color{red}5\\ \color{green}1&\color{green}3&\color{green}5\\ \color{green}1&\color{green}3&\color{green}5 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{1162}=\operatorname{ryser}(G_{1030},15, 26)\)

Pair (1032, 1164)

Graph 1032

Graph 1164

\(\begin{pmatrix} \color{red}1&\color{red}2&\color{red}5&\color{red}11\\ \color{red}1&\color{red}2&\color{red}5&\color{red}11\\ \color{blue}1&\color{blue}2&\color{blue}6&\color{blue}12\\ \color{green}1&\color{green}0&\color{green}0&\color{green}0\\ \color{red}1&\color{red}2&\color{red}5&\color{red}11\\ \color{red}1&\color{red}2&\color{red}5&\color{red}11\\ \color{yellow}1&\color{yellow}3&\color{yellow}6&\color{yellow}16\\ \color{yellow}1&\color{yellow}3&\color{yellow}6&\color{yellow}16 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{1164}=\operatorname{ryser}(G_{1032},15, 26)\)

Pair (1105, 1235)

Graph 1105

Graph 1235

\(\begin{pmatrix} \color{red}1&\color{red}2&\color{red}6\\ \color{red}1&\color{red}2&\color{red}6\\ \color{blue}1&\color{blue}2&\color{blue}8\\ \color{blue}1&\color{blue}2&\color{blue}8\\ \color{red}1&\color{red}2&\color{red}6\\ \color{red}1&\color{red}2&\color{red}6\\ \color{green}1&\color{green}4&\color{green}8\\ \color{green}1&\color{green}4&\color{green}8 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{1235}=\operatorname{ryser}(G_{1105},15, 26)\)

Pair (3392, 3494)

Graph 3392

Graph 3494

\(\begin{pmatrix} \color{red}1&\color{red}2\\ \color{red}1&\color{red}2\\ \color{red}1&\color{red}2\\ \color{red}1&\color{red}2\\ \color{blue}1&\color{blue}3\\ \color{blue}1&\color{blue}3\\ \color{blue}1&\color{blue}3\\ \color{blue}1&\color{blue}3 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{3494}=\operatorname{ryser}(G_{3392},57, 68)\)

Pair (3482, 3592)

Graph 3482

Graph 3592

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}11\\ \color{blue}1&\color{blue}2&\color{blue}7\\ \color{red}1&\color{red}3&\color{red}11\\ \color{blue}1&\color{blue}2&\color{blue}7\\ \color{green}1&\color{green}3&\color{green}9\\ \color{green}1&\color{green}3&\color{green}9\\ \color{yellow}1&\color{yellow}4&\color{yellow}11\\ \color{yellow}1&\color{yellow}4&\color{yellow}11 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{3592}=\operatorname{ryser}(G_{3482},25, 46)\)

Pair (3413, 3779)

Graph 3413

Graph 3779

\(\begin{pmatrix} \color{red}1&\color{red}2\\ \color{red}1&\color{red}2\\ \color{red}1&\color{red}2\\ \color{red}1&\color{red}2\\ \color{blue}1&\color{blue}3\\ \color{blue}1&\color{blue}3\\ \color{blue}1&\color{blue}3\\ \color{blue}1&\color{blue}3 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{3779}=\operatorname{ryser}(G_{3413},15, 48)\)

Pair (1270, 5629)

Graph 1270

Graph 5629

\(\begin{pmatrix} \color{red}1&\color{red}1\\ \color{blue}1&\color{blue}2\\ \color{blue}1&\color{blue}2\\ \color{blue}1&\color{blue}2\\ \color{red}1&\color{red}1\\ \color{blue}1&\color{blue}2\\ \color{blue}1&\color{blue}2\\ \color{blue}1&\color{blue}2 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{5629}=\operatorname{ryser}(G_{1270},26, 48)\)

Pair (5684, 5718)

Graph 5684

Graph 5718

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}11\\ \color{blue}1&\color{blue}2&\color{blue}6\\ \color{blue}1&\color{blue}2&\color{blue}6\\ \color{red}1&\color{red}3&\color{red}11\\ \color{blue}1&\color{blue}2&\color{blue}6\\ \color{blue}1&\color{blue}2&\color{blue}6\\ \color{green}1&\color{green}4&\color{green}10\\ \color{green}1&\color{green}4&\color{green}10 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{5718}=\operatorname{ryser}(G_{5684},25, 36)\)

Pair (3887, 5753)

Graph 3887

Graph 5753

\(\begin{pmatrix} \color{red}1&\color{red}2\\ \color{blue}1&\color{blue}3\\ \color{blue}1&\color{blue}3\\ \color{green}1&\color{green}0\\ \color{blue}1&\color{blue}3\\ \color{blue}1&\color{blue}3\\ \color{red}1&\color{red}2\\ \color{yellow}1&\color{yellow}4 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{5753}=\operatorname{ryser}(G_{3887},15, 37)\)

Pair (3899, 5755)

Graph 3899

Graph 5755

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}12\\ \color{red}1&\color{red}3&\color{red}12\\ \color{red}1&\color{red}3&\color{red}12\\ \color{blue}1&\color{blue}0&\color{blue}0\\ \color{red}1&\color{red}3&\color{red}12\\ \color{red}1&\color{red}3&\color{red}12\\ \color{red}1&\color{red}3&\color{red}12\\ \color{green}1&\color{green}6&\color{green}18 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{5755}=\operatorname{ryser}(G_{3899},15, 37)\)

Pair (3886, 5756)

Graph 3886

Graph 5756

\(\begin{pmatrix} \color{red}1&\color{red}2\\ \color{red}1&\color{red}2\\ \color{blue}1&\color{blue}3\\ \color{green}1&\color{green}1\\ \color{blue}1&\color{blue}3\\ \color{red}1&\color{red}2\\ \color{red}1&\color{red}2\\ \color{blue}1&\color{blue}3 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{5756}=\operatorname{ryser}(G_{3886},15, 37)\)

Pair (3888, 5759)

Graph 3888

Graph 5759

\(\begin{pmatrix} \color{red}1&\color{red}2&\color{red}6&\color{red}20\\ \color{blue}1&\color{blue}3&\color{blue}10&\color{blue}29\\ \color{blue}1&\color{blue}3&\color{blue}10&\color{blue}29\\ \color{green}1&\color{green}1&\color{green}5&\color{green}13\\ \color{blue}1&\color{blue}3&\color{blue}10&\color{blue}29\\ \color{blue}1&\color{blue}3&\color{blue}10&\color{blue}29\\ \color{red}1&\color{red}2&\color{red}6&\color{red}20\\ \color{yellow}1&\color{yellow}5&\color{yellow}13&\color{yellow}45 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{5759}=\operatorname{ryser}(G_{3888},15, 37)\)

Pair (3903, 5761)

Graph 3903

Graph 5761

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}13\\ \color{red}1&\color{red}3&\color{red}13\\ \color{red}1&\color{red}3&\color{red}13\\ \color{blue}1&\color{blue}1&\color{blue}7\\ \color{red}1&\color{red}3&\color{red}13\\ \color{red}1&\color{red}3&\color{red}13\\ \color{red}1&\color{red}3&\color{red}13\\ \color{green}1&\color{green}7&\color{green}19 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{5761}=\operatorname{ryser}(G_{3903},15, 37)\)

Pair (6471, 7012)

Graph 6471

Graph 7012

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}10&\color{red}32&\color{red}102\\ \color{red}1&\color{red}3&\color{red}10&\color{red}32&\color{red}102\\ \color{blue}1&\color{blue}2&\color{blue}8&\color{blue}22&\color{blue}78\\ \color{green}1&\color{green}2&\color{green}7&\color{green}21&\color{green}71\\ \color{green}1&\color{green}2&\color{green}7&\color{green}21&\color{green}71\\ \color{yellow}1&\color{yellow}4&\color{yellow}11&\color{yellow}39&\color{yellow}117\\ \color{yellow}1&\color{yellow}4&\color{yellow}11&\color{yellow}39&\color{yellow}117\\ \color{orange}1&\color{orange}4&\color{orange}14&\color{orange}42&\color{orange}142 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{7012}=\operatorname{ryser}(G_{6471},14, 25)\)

Pair (6479, 7013)

Graph 6479

Graph 7013

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}8\\ \color{red}1&\color{red}3&\color{red}8\\ \color{blue}1&\color{blue}3&\color{blue}9\\ \color{green}1&\color{green}2&\color{green}6\\ \color{green}1&\color{green}2&\color{green}6\\ \color{red}1&\color{red}3&\color{red}8\\ \color{red}1&\color{red}3&\color{red}8\\ \color{blue}1&\color{blue}3&\color{blue}9 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{7013}=\operatorname{ryser}(G_{6479},14, 25)\)

Pair (6481, 7015)

Graph 6481

Graph 7015

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}11&\color{red}37\\ \color{red}1&\color{red}3&\color{red}11&\color{red}37\\ \color{blue}1&\color{blue}3&\color{blue}13&\color{blue}43\\ \color{green}1&\color{green}2&\color{green}7&\color{green}24\\ \color{green}1&\color{green}2&\color{green}7&\color{green}24\\ \color{yellow}1&\color{yellow}4&\color{yellow}13&\color{yellow}48\\ \color{yellow}1&\color{yellow}4&\color{yellow}13&\color{yellow}48\\ \color{orange}1&\color{orange}5&\color{orange}17&\color{orange}61 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{7015}=\operatorname{ryser}(G_{6481},14, 25)\)

Pair (6476, 7026)

Graph 6476

Graph 7026

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}10\\ \color{red}1&\color{red}3&\color{red}10\\ \color{blue}1&\color{blue}2&\color{blue}6\\ \color{red}1&\color{red}3&\color{red}10\\ \color{red}1&\color{red}3&\color{red}10\\ \color{green}1&\color{green}3&\color{green}8\\ \color{green}1&\color{green}3&\color{green}8\\ \color{yellow}1&\color{yellow}4&\color{yellow}12 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{7026}=\operatorname{ryser}(G_{6476},14, 25)\)

Pair (6478, 7028)

Graph 6478

Graph 7028

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}13\\ \color{red}1&\color{red}3&\color{red}13\\ \color{blue}1&\color{blue}2&\color{blue}8\\ \color{red}1&\color{red}3&\color{red}13\\ \color{red}1&\color{red}3&\color{red}13\\ \color{green}1&\color{green}4&\color{green}14\\ \color{green}1&\color{green}4&\color{green}14\\ \color{yellow}1&\color{yellow}6&\color{yellow}20 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{7028}=\operatorname{ryser}(G_{6478},14, 25)\)

Pair (6486, 7035)

Graph 6486

Graph 7035

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}11&\color{red}35\\ \color{red}1&\color{red}3&\color{red}11&\color{red}35\\ \color{blue}1&\color{blue}3&\color{blue}11&\color{blue}33\\ \color{red}1&\color{red}3&\color{red}11&\color{red}35\\ \color{red}1&\color{red}3&\color{red}11&\color{red}35\\ \color{green}1&\color{green}3&\color{green}9&\color{green}33\\ \color{green}1&\color{green}3&\color{green}9&\color{green}33\\ \color{yellow}1&\color{yellow}5&\color{yellow}15&\color{yellow}55 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{7035}=\operatorname{ryser}(G_{6486},14, 25)\)

Pair (6488, 7037)

Graph 6488

Graph 7037

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}14&\color{red}53\\ \color{red}1&\color{red}3&\color{red}14&\color{red}53\\ \color{blue}1&\color{blue}3&\color{blue}15&\color{blue}55\\ \color{red}1&\color{red}3&\color{red}14&\color{red}53\\ \color{red}1&\color{red}3&\color{red}14&\color{red}53\\ \color{green}1&\color{green}4&\color{green}16&\color{green}66\\ \color{green}1&\color{green}4&\color{green}16&\color{green}66\\ \color{yellow}1&\color{yellow}7&\color{yellow}23&\color{yellow}103 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{7037}=\operatorname{ryser}(G_{6488},14, 25)\)

Pair (10840, 10851)

Graph 10840

Graph 10851

\(\begin{pmatrix} \color{red}1&\color{red}3\\ \color{red}1&\color{red}3\\ \color{blue}1&\color{blue}4\\ \color{blue}1&\color{blue}4\\ \color{red}1&\color{red}3\\ \color{red}1&\color{red}3\\ \color{blue}1&\color{blue}4\\ \color{blue}1&\color{blue}4 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{10851}=\operatorname{ryser}(G_{10840},14, 36)\)

Pair (5358, 11716)

Graph 5358

Graph 11716

\(\begin{pmatrix} \color{red}1\\ \color{red}1\\ \color{red}1\\ \color{red}1\\ \color{red}1\\ \color{red}1\\ \color{red}1\\ \color{red}1 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{11716}=\operatorname{ryser}(\operatorname{ryser}(G_{5358},16, 25),38,47)\)

Pair (10867, 11731)

Graph 10867

Graph 11731

\(\begin{pmatrix} \color{red}1&\color{red}3\\ \color{red}1&\color{red}3\\ \color{blue}1&\color{blue}4\\ \color{blue}1&\color{blue}4\\ \color{red}1&\color{red}3\\ \color{red}1&\color{red}3\\ \color{blue}1&\color{blue}4\\ \color{blue}1&\color{blue}4 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{11731}=\operatorname{ryser}(G_{10867},15, 26)\)

Pair (10841, 11742)

Graph 10841

Graph 11742

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}12\\ \color{red}1&\color{red}3&\color{red}12\\ \color{blue}1&\color{blue}4&\color{blue}16\\ \color{blue}1&\color{blue}4&\color{blue}16\\ \color{red}1&\color{red}3&\color{red}12\\ \color{red}1&\color{red}3&\color{red}12\\ \color{green}1&\color{green}5&\color{green}19\\ \color{green}1&\color{green}5&\color{green}19 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{11742}=\operatorname{ryser}(G_{10841},14, 36)\)

Pair (10838, 11747)

Graph 10838

Graph 11747

\(\begin{pmatrix} \color{red}1&\color{red}2&\color{red}8\\ \color{blue}1&\color{blue}4&\color{blue}14\\ \color{blue}1&\color{blue}4&\color{blue}14\\ \color{blue}1&\color{blue}4&\color{blue}14\\ \color{blue}1&\color{blue}4&\color{blue}14\\ \color{red}1&\color{red}2&\color{red}8\\ \color{green}1&\color{green}4&\color{green}16\\ \color{green}1&\color{green}4&\color{green}16 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{11747}=\operatorname{ryser}(G_{10838},14, 36)\)

Pair (10839, 11748)

Graph 10839

Graph 11748

\(\begin{pmatrix} \color{red}1&\color{red}2&\color{red}8\\ \color{blue}1&\color{blue}4&\color{blue}16\\ \color{blue}1&\color{blue}4&\color{blue}16\\ \color{blue}1&\color{blue}4&\color{blue}16\\ \color{blue}1&\color{blue}4&\color{blue}16\\ \color{red}1&\color{red}2&\color{red}8\\ \color{green}1&\color{green}5&\color{green}21\\ \color{green}1&\color{green}5&\color{green}21 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{11748}=\operatorname{ryser}(G_{10839},14, 36)\)

Pair (10849, 11751)

Graph 10849

Graph 11751

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}14&\color{red}56\\ \color{blue}1&\color{blue}4&\color{blue}17&\color{blue}69\\ \color{blue}1&\color{blue}4&\color{blue}17&\color{blue}69\\ \color{blue}1&\color{blue}4&\color{blue}17&\color{blue}69\\ \color{blue}1&\color{blue}4&\color{blue}17&\color{blue}69\\ \color{red}1&\color{red}3&\color{red}14&\color{red}56\\ \color{green}1&\color{green}4&\color{green}16&\color{green}68\\ \color{yellow}1&\color{yellow}6&\color{yellow}22&\color{yellow}96 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{11751}=\operatorname{ryser}(G_{10849},14, 36)\)

Pair (10850, 11752)

Graph 10850

Graph 11752

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}15\\ \color{blue}1&\color{blue}4&\color{blue}19\\ \color{blue}1&\color{blue}4&\color{blue}19\\ \color{blue}1&\color{blue}4&\color{blue}19\\ \color{blue}1&\color{blue}4&\color{blue}19\\ \color{red}1&\color{red}3&\color{red}15\\ \color{green}1&\color{green}5&\color{green}23\\ \color{yellow}1&\color{yellow}7&\color{yellow}27 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{11752}=\operatorname{ryser}(G_{10850},14, 36)\)

Pair (10887, 11755)

Graph 10887

Graph 11755

\(\begin{pmatrix} \color{red}1&\color{red}3&\color{red}13\\ \color{blue}1&\color{blue}4&\color{blue}17\\ \color{blue}1&\color{blue}4&\color{blue}17\\ \color{blue}1&\color{blue}4&\color{blue}17\\ \color{blue}1&\color{blue}4&\color{blue}17\\ \color{red}1&\color{red}3&\color{red}13\\ \color{green}1&\color{green}5&\color{green}19\\ \color{green}1&\color{green}5&\color{green}19 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{11755}=\operatorname{ryser}(G_{10887},14, 36)\)

Pair (10897, 11761)

Graph 10897

Graph 11761

\(\begin{pmatrix} \color{red}1&\color{red}4\\ \color{red}1&\color{red}4\\ \color{red}1&\color{red}4\\ \color{red}1&\color{red}4\\ \color{red}1&\color{red}4\\ \color{red}1&\color{red}4\\ \color{blue}1&\color{blue}6\\ \color{blue}1&\color{blue}6 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{11761}=\operatorname{ryser}(G_{10897},14, 36)\)

Pair (10898, 11762)

Graph 10898

Graph 11762

\(\begin{pmatrix} \color{red}1&\color{red}4\\ \color{red}1&\color{red}4\\ \color{red}1&\color{red}4\\ \color{red}1&\color{red}4\\ \color{red}1&\color{red}4\\ \color{red}1&\color{red}4\\ \color{blue}1&\color{blue}7\\ \color{blue}1&\color{blue}7 \end{pmatrix}\)

Walk Matrix

CDC

Ryser Switch
\(G_{11762}=\operatorname{ryser}(G_{10898},14, 36)\)