Article in volume
Authors:
Title:
Biregular (and regular) planar cages
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 1171-1194
Received: 2020-09-02 , Revised: 2021-07-02 , Accepted: 2021-07-02 , Available online: 2021-07-29 , https://doi.org/10.7151/dmgt.2425
Abstract:
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\leq r < 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
References:
- E. Abajo and A. Diánez, Exact values of $ex(\nu;\{C_3,C_4, \ldots,C_n\})$, Discrete Appl. Math. 158 (2010) 1869–1878.
https://doi.org/10.1016/j.dam.2010.08.002 - 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 - 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 - 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 - 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.
- 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 - G. Araujo-Pardo, R. Jajcay and A. Ramos Rivera, On a relation between bipartite biregular cages, block designs and generalized polygons, submitted.
- G. Araujo-Pardo and G.N. López, On new record graphs close to bipartite Moore graphs, submitted.
- G. Brinkmann and B.D. McKay, Fast generation of planar graphs $($expanded version$)$.
https://users.cecs.anu.edu.au/~bdm/plantri - 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 - G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs (6th Ed., Chapman and Hall, 2015).
https://doi.org/10.1201/b19731 - 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.
- G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Combin., Dynamic Surveys (2013) #DS16.
https://doi.org/10.37236/37 - 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 - S. Filipovski, On bipartite cages of excess $4$, Electron. J. Combin. 24(1) (2017) #P1.40.
https://doi.org/10.37236/6693 - 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 - 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 - 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 - 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 - The Sage Developers, Sagemath, the Sage Mathematics Software System, Version $8.4$ (2018).
https://www.sagemath.org - W.T. Tutte, A family of cubical graphs, Math. Proc. Cambridge Philos. Soc. 43 (1947) 459–474.
https://doi.org/10.1017/S0305004100023720
Close