antennense

2022-07-08

Pairwise Non Isomorphic 3-regular Graphs of certain orders
I am currently reviewing some graph theory before an exam and ran into the following problem which has me fairly stumped.
The number of pairwise non-isomorphic 3-regular graphs of order 8 is 6, the number of pairwise non-isomorphic 3-regular graphs of order 10 is 21, and the number of pairwise non-isomorphic 3-regular graphs of order 14 is 540. Using this information, determine the number of pairwise non-isomorphic connected 3-regular graphs of order 14.
I know that pairwise non-isomorphic graphs means that no two graphs in the set of graphs for a said order should be the same, i.e. it should have a bijection in each pair of graph's vertex sets.
However, I'm unsure how to utilise the previous orders to determine the number when the order is 14.
Any hints and help regarding this would be appreciated.

Hayley Mccarthy

Expert

Step 1
If a cubic graph of order 14 is not connected, then it has one of the following three sets of components: 4, 4, 6; 6, 8; 4, 10.
For 4, 4, 6 there are 2 cubic graphs;
for 6, 8 there are 12 cubic graphs;
for 4, 10 there are 21 cubic graphs.
Step 2
But two graphs for 4, 4, 6 are counted three times. Therefore we get $21+12+2-4=31$ and there are 509 connected cubic graphs of order 14.

cdsommegolfzp

Expert

Step 1
We use cubic instead of 3-regular.
We are tasked with finding the number of isomorphism types for cubic graphs of degree 3 that are connected.
We are told there is 540 isomorphism types for cubic graphs on 14 vertices total, so we must only count the disconnected isomorphism types and substract it from this number, fortunately these ones are easy to do.
The connected components of such a graph can have sizes 4,6,8 or 10 (12 isn't possible because 2 is not possible).
Hence we just have to iterate over the partitions of 14 into sizes from this list and see how many possibilities each allows. There can be at most 3 summands and the only one with 3 summands is (4,4,6), the other options have two summands and it is easy to see they are (4,10) and (6,8)
Option 1 is (4,4,6). Note there is only one cubic connected graph with 4 vertices so those components must be ${K}_{4}$, there are two isomorphism types with 6 vertices though. Hence there is 2 isomorphism types with components of sizes (4,4,6).
Step 2
Option 2 is (4,10), there are $1\cdot 1\cdot 21$. One component must be ${K}_{4}$ and the other has 21 options, so there are 21 isomorphism types with sizes (4,10).
Step 3
Option 3 is (6,8), there are 2 options for the component of size 6 and 6 for the component of size 8.
Hence there are $2+21+12=35$ isomorphism types for cubic disconnected graphs of order 14.

Do you have a similar question?