Loading...
Loading...

Go to the content (press return)

On the order of graphs with a given girth pair

Author
Balbuena, C.; Salas, J.
Type of activity
Journal article
Journal
Discrete mathematics
Date of publication
2014-04-28
Volume
321
First page
68
Last page
75
DOI
https://doi.org/10.1016/j.disc.2013.12.015 Open in new window
Project funding
Control de invariantes en grafos sujetos a propiedades estructurales
URL
http://www.sciencedirect.com/science/article/pii/S0012365X13005268 Open in new window
Abstract
A (k; g, h)-graph is a k-regular graph of girth pair (g, h) where g is the girth of the graph, h is the length of a smallest cycle of different parity than g and g < h. A (k; g, h)-cage is a (k; g, h)-graph with the least possible number of vertices denoted by n(k; g, h). In this paper we give a lower bound on n(k; g, h) and as a consequence we establish that every (k; 6)-cage is bipartite if it is free of odd cycles of length at most 2k - 1. This is a contribution to the conjecture claiming tha...
Keywords
CAGES, Cages, Excess, Girth pair, REGULAR GRAPHS
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications

Participants