Balbuena, Camino and Marcote, Xavier and Gonzalez-Moreno, Diego - Some properties of semiregular cages

dmtcs:499 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 5
Some properties of semiregular cages

Authors: Balbuena, Camino and Marcote, Xavier and Gonzalez-Moreno, Diego

A graph with degree set \r, r + 1\ is said to be semiregular. A semiregular cage is a semiregular graph with given girth g and the least possible order. First, an upper bound on the diameter of semiregular graphs with girth g and order close enough to the minimum possible value is given in this work. As a consequence, these graphs are proved to be maximally connected when the girth g >= 7 is odd. Moreover an upper bound for the order of semiregular cages is given and, as an application, every semiregular cage with degree set \r, r + 1\ is proved to be maximally connected for g is an element of \6, 8\, and when g = 12 for r >= 7 and r not equal 20. Finally it is also shown that every (\r, r + 1\; g)-cage is 3-connected.


Source : oai:HAL:hal-00990460v1
Volume: Vol. 12 no. 5
Section: Graph and Algorithms
Published on: January 1, 2010
Submitted on: March 26, 2015
Keywords: cage,degree set,girth,connectivity,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 53 times.
This article's PDF has been downloaded 31 times.