What are "different" bipartite regular graphs?

214 Views Asked by At

I am struggeling with the idea that there are multiple CONNECTED $d$-regular bipartite graphs for fixed degree $d$ and number of vertices $2n$. If I just draw the vertices in two columns calling the vertices in column 1 $(v_{1,1},...,v_{1,n})$ and in column 2 $(v_{2,1},...,v_{2,n})$ and draw the corresponding edges then in my head for any other $d$-regular bipartite graph I can just apply permutations to $\sigma_1,\sigma_2$ to column 1 and column 2, respectively, and I obtain any other CONNECTED bipartite regular graph.

Are there multiple $d$-regular bipartite graphs in the sens that they are qualitatively different? Like for normal $d$-regular graphs where the properties may vary a lot between different example?

EDIT: I should emphasize that I am talking about connected graphs!

1

There are 1 best solutions below

2
On BEST ANSWER

Already for $d=2$ you can have different possibilities based on what the connected components look like. If $2n=8$, for instance, the vertices can be arranged in a single $8$-cycle, or in two $4$-cycles. For larger $d$, you have even more flexibility.

If you want a connected example, then we'll need $d \ge 3$, just as with ordinary $d$-regular graphs. But we can still find an easy counterexample if we take bipartite complements (that is, change adjacencies between the two halves only). For example, the bipartite complement of $C_4 \cup C_6$ and the bipartite complement of $C_{10}$ are non-isomorphic $3$-regular graphs on $10$ vertices.

Really, the greatest variety is found in the cases I'm not looking at: $3 \le d \le n-3$. But those are also harder to describe, and harder to check for isomorphism.