Small bi-regular graphs of even girth

详细信息    查看全文

• 作者：Gabriela Araujo-Pardo^a ; ^{garaujo@math.unam.mx" class="auth_mail" title="E-mail the corresponding author} ; Geoffrey Exoo^b ; ^{ge@cs.indstate.edu" class="auth_mail" title="E-mail the corresponding author} ; Robert Jajcay^c ; ^{robert.jajcay@fmph.uniba.sk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Cage ; Bi-regular cage ; Recursive construction ; Order
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：658-667
• 全文大小：406 K

文摘

A graph of girth g$g$ that contains vertices of degrees r$r$ and m$m$ is called a bi-regular ({r,m},g)$(\{r,m\},g)$-graph. As with the Cage Problem  , we seek the smallest ({r,m},g)$(\{r,m\},g)$-graphs for given parameters 2≤r<m$2\le r<m$, g≥3$g\ge 3$, called ({r,m},g)$(\{r,m\},g)$-cages. The orders of the majority of ({r,m},g)$(\{r,m\},g)$-cages, in cases where m$m$ is much larger than r$r$ and the girth g$g$ is odd, have been recently determined via the construction of an infinite family of graphs whose orders match a well-known lower bound, but a generalization of this result to bi-regular cages of even girth proved elusive.

We summarize and improve some of the previously established lower bounds for the orders of bi-regular cages of even girth and present a generalization of the odd girth construction to even girths that provides us with a new general upper bound on the order of graphs with girths of the form g=2t$g=2t$, t$t$ odd. This construction produces infinitely many ({r,m};6)$(\{r,m\};6)$-cages with sufficiently large m$m$. We also determine a dafea6108c" title="Click to view the MathML source">({3,4};10)$(\{3,4\};10)$-cage of order 82.