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]

This page has been seen 114 times.

This article's PDF has been downloaded 279 times.