1
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ For $d=0,1,2,n,n-1,n-2$, there is only one possible such graph, up to permutations. Otherwise, there could be different graphs $\endgroup$ – Exodd Apr 14 at 15:48
  • $\begingroup$ This website (hog.grinvin.org/Cubic) lists cubic (that is, $3$-regular) graphs by vertex count and girth, restricted to connected graphs, and additionally has a table restricting the lists to bipartite graphs. The smallest example of what you're looking for is the two distinct $10$-vertex $3$-regular bipartite connected graphs. $\endgroup$ – mjqxxxx Apr 14 at 17:12
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks! I clarified in the question that I am looking only for connected graphs. $\endgroup$ – Jfischer Apr 14 at 16:07
  • $\begingroup$ So take bipartite complements and now you're looking at many different connected $(n-2)$-regular bipartite graphs. $\endgroup$ – Misha Lavrov Apr 14 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.