Geodesic
Biregular (and regular) planar cages
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1171-1194 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

We study the Cage Problem for biregular planar graphs. This problem has being widely studied for biregular graphs (without the planarity hypothesis). An ({r,m};g)-graph is a biregular graph whose vertices have degrees r and m, for 2≤ r lt; m, and girth g. An ({r,m};g)-cage is an ({r,m};g)-graph of minimum order. In this paper, we determine the triplets of values ( { r, m } ; g) for which there exist planar ({ r, m } ; g)-graphs and for all values we construct examples. Furthermore, we bound the order of the ( { r, m } ; g)-cages and in many instances we build examples that reach the bounds.
Keywords: cages, biregular cages, planar graphs 
@article{DMGT_2023_43_4_a15,
     author = {Araujo-Pardo, Gabriela and Barrera-Cruz, Fidel and Garc{\'\i}a-Col{\'\i}n, Natalia},
     title = {Biregular (and regular) planar cages},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1171--1194},
     year = {2023},
     volume = {43},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a15/}
}
TY  - JOUR
AU  - Araujo-Pardo, Gabriela
AU  - Barrera-Cruz, Fidel
AU  - García-Colín, Natalia
TI  - Biregular (and regular) planar cages
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 1171
EP  - 1194
VL  - 43
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a15/
LA  - en
ID  - DMGT_2023_43_4_a15
ER  - 
%0 Journal Article
%A Araujo-Pardo, Gabriela
%A Barrera-Cruz, Fidel
%A García-Colín, Natalia
%T Biregular (and regular) planar cages
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 1171-1194
%V 43
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a15/
%G en
%F DMGT_2023_43_4_a15
Araujo-Pardo, Gabriela; Barrera-Cruz, Fidel; García-Colín, Natalia. Biregular (and regular) planar cages. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1171-1194. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a15/

[1] E. Abajo and A. Diánez, Exact values of ex(\nu;{C3,C4, \ldots,Cn}), Discrete Appl. Math. 158 (2010) 1869–1878. https://doi.org/10.1016/j.dam.2010.08.002

[2] M. Abreu, G. Araujo-Pardo, C. Balbuena, D. Labbate and G. López-Chávez, Biregular cages of girth five, Electron. J. Combin. 20(1) (2013) #P71. https://doi.org/10.37236/2594

[3] G. Araujo-Pardo, C. Balbuena, G. López-Chávez and L. Montejano, On bi-regular cages of even girth at least 8, Aequationes Math. 86 (2013) 201–216. https://doi.org/10.1007/s00010-013-0227-5

[4] G. Araujo-Pardo, G. Exoo and R. Jajcay, Small bi-regular graphs of even girth, Discrete Math. 339 (2016) 658–667. https://doi.org/10.1016/j.disc.2015.10.009

[5] G. Araujo, D. González, J.J. Montellano-Ballesteros and O. Serra, On upper bounds and connectivity of cages, Australas. J. Combin. 38 (2007) 221–228.

[6] G. Araujo-Pardo, C. Hernández-Cruz and J.J. Montellano-Ballesteros, Mixed cages, Graphs Combin. 35 (2019) 989–999. https://doi.org/10.1007/s00373-019-02050-1

[7] G. Araujo-Pardo, R. Jajcay and A. Ramos Rivera, On a relation between bipartite biregular cages, block designs and generalized polygons, submitted.

[8] G. Araujo-Pardo and G.N. López, On new record graphs close to bipartite Moore graphs, submitted.

[9] G. Brinkmann and B.D. McKay, Fast generation of planar graphs (expanded version). https://users.cecs.anu.edu.au/~bdm/plantri

[10] G. Chartrand, R.J. Gould and S.F. Kapoor, Graphs with prescribed degree sets and girth, Period. Math. Hungar. 12 (1981) 261–266. https://doi.org/10.1007/BF01849614

[11] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs (6th Ed., Chapman and Hall, 2015). https://doi.org/10.1201/b19731

[12] P. Erdős and H. Sachs, Regulare Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math-Nat. 12 (1963) 251–258.

[13] G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Combin., Dynamic Surveys (2013) #DS16. https://doi.org/10.37236/37

[14] G. Exoo and R. Jajcay, Bi-regular cages of odd girth, J. Graph Theory 81 (2016) 50–56. https://doi.org/10.1002/jgt.21860

[15] S. Filipovski, On bipartite cages of excess 4, Electron. J. Combin. 24(1) (2017) #P1.40. https://doi.org/10.37236/6693

[16] S. Filipovski, A. Ramos Rivera and R. Jajcay, On biregular bipartite graphs of small excess, Discrete Math. 342 (2019) 2066–2076. https://doi.org/10.1016/j.disc.2019.04.004

[17] F. Garbe, On graphs with excess or defect 2, Discrete Appl. Math. 180 (2015) 81–88. https://doi.org/10.1016/j.dam.2014.07.022

[18] S.F. Kapoor, A.D. Polimeni and C.E. Wall, Degree sets for graphs, Fund. Math. 95 (1977) 189–194. https://doi.org/10.4064/fm-95-3-189-194

[19] M. Miller and J. Sirán, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin., Dynamic Surveys (2013) #DS14. https://doi.org/10.37236/35

[20] The Sage Developers, Sagemath, the Sage Mathematics Software System, Version 8.4 (2018). https://www.sagemath.org

[21] W.T. Tutte, A family of cubical graphs, Math. Proc. Cambridge Philos. Soc. 43 (1947) 459–474. https://doi.org/10.1017/S0305004100023720