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 cages

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

  • 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]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.46298/dmtcs.461
  • 10.46298/dmtcs.461
  • 10.46298/dmtcs.461
A construction of small regular bipartite graphs of girth 8

Consultation statistics

This page has been seen 255 times.
This article's PDF has been downloaded 388 times.