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

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

Authors: Camino Balbuena ORCID1; Xavier Marcote 1; Diego Gonzalez-Moreno ORCID1

  • 1 Departament de Matematica Aplicada III [Barcelona]

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.

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

Consultation statistics

This page has been seen 374 times.
This article's PDF has been downloaded 467 times.