Uniquely bi-embeddable bipartite 2-regular graphs

Hong Wang; Jiayu Yang

doi:10.56754/0719-0646.2901.007

Authors

Hong Wang Department of Mathematics and Statistical Science, University of Idaho, Moscow 83844-1103, Idaho, USA https://orcid.org/0000-0003-0803-1111
Jiayu Yang Department of Mathematics and Statistical Science, University of Idaho, Moscow 83844-1103, Idaho, USA https://orcid.org/0009-0003-8217-4396

MSC:

05C35, 05C38, 05C60

DOI:

https://doi.org/10.56754/0719-0646.2901.007

Keywords:

Bi-embeddings, bipartite graphs, disjoint union of cycles

Abstract

A bipartite 2-regular graph is a bipartite graph \(G\) such that \(G = C_{2n_{1}} \cup C_{2n_{2}} \cup \cdots \cup C_{2n_{k}}\) with \(k \geq 1\), i.e., \(G\) is a vertex-disjoint union of bipartite cycles. In this paper, we completely characterize the bipartite 2-regular graphs which can be uniquely bi-embedded into their bipartite complements.

References

[1] B. Bollobás, Extremal graph theory, ser. Lond. Math. Soc. Monogr. Academic Press, London, 1978, vol. 11.

[2] I. Grzelec, M. Pilśniak, and M. Woźniak, “A note on uniquely embeddable 2-factors,” Appl. Math. Comput., vol. 468, 2024, Art. ID 128505, doi: 10.1016/j.amc.2023.128505.

[3] J. Otfinowska and M. Woźniak, “A note on uniquely embeddable forests,” Discuss. Math., Graph Theory, vol. 33, no. 1, pp. 193–201, 2013, doi: 10.7151/dmgt.1651.

[4] N. Sauer and J. Spencer, “Edge disjoint placement of graphs,” J. Comb. Theory, Ser. B, vol. 25, pp. 295–302, 1978, doi: 10.1016/0095-8956(78)90005-9.

[5] H. Wang, “Packing two bipartite graphs into a complete bipartite graph,” J. Graph Theory, vol. 26, no. 2, pp. 95–104, 1997, doi: 10.1002/(SICI)1097-0118(199710)26:2<95::AID-JGT4>3.0.CO;2-A.

[6] H. Wang, “Bipacking a bipartite graph with girth at least 12,” J. Korean Math. Soc., vol. 56, no. 1, pp. 25–37, 2019, doi: 10.4134/JKMS.j180002.

[7] M. Woźniak, “Packing of graphs,” Diss. Math., vol. 362, 1997.

[8] M. Woźniak, “A note on uniquely embeddable graphs,” Discuss. Math., Graph Theory, vol. 18, no. 1, pp. 15–21, 1998, doi: 10.7151/dmgt.1060.

[9] M. Woźniak, “Packing of graphs and permutations—a survey,” Discrete Math., vol. 276, no. 1-3, pp. 379–391, 2004, doi: 10.1016/S0012-365X(03)00296-6.

[10] J. Yang and H. Wang, “Proof of a packing conjecture of bipartite graphs,” Australas. J. Comb., vol. 94, no. 3, pp. 316–332, 2026.

[11] H. P. Yap, “Packing of graphs—a survey,” Discrete Math., vol. 72, no. 1-3, pp. 395–404, 1988, doi: 10.1016/0012-365X(88)90232-4.