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 - https://doi.org/10.46298/dmtcs.499
Some properties of semiregular cages

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

    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]

    Share

    Consultation statistics

    This page has been seen 194 times.
    This article's PDF has been downloaded 324 times.