On the monotonicity of \((k;g,h)\)-graphs
type: Item
instance of: scholarly article
title: On the monotonicity of \((k;g,h)\)-graphs
zbMATH Open document ID: 1013.05041
author: Ping Wang
author: Bao-guang Xu
author: Jianfang Wang
published in: Acta Mathematicae Applicatae Sinica. English Series
publication date: 2003-06-22T00:00:00Z
review text: A \(k\)-regular graph with girth \(g\) is called a \((k;g)\)-graph. A \((k;g)\)-cage is a \((k;g)\)-graph with the least possible number of vertices. The number of vertices of a \((k;g)\)-cage is denoted by \(f(k;g)\). The odd and even girths of a graph \(G\) are the lengths of a shortest odd and even cycle of \(G\) respectively. A \(k\)-regular graph with odd and even girths \(g\) and \(h\) (\(g\) is the smaller of the numbers of odd and even girths) is called a \((k;g,h)\)-graph. A \((k;g,h)\)-cage is a \((k;g,h)\)-graph with the least possible number of vertices. The number of vertices of a \((k;g,h)\)-cage is denoted by \(f(k;g,h)\). It is proved that \(f(k;h-1,h)<f(k;h)\) for \(k\geq 3, h\geq 4\). This result strengthens an inequality proved by \textit{F. Harary} and \textit{P. Kovács} [J. Graph Theory 7, 209-218 (1983; Zbl 0542.05041)].
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1885790
zbMATH Keywords: cages graph
zbMATH Keywords: regular graph
zbMATH Keywords: odd girth
zbMATH Keywords: even girth
reviewed by: Gabriel Semanišin
MaRDI profile type: Publication
full work available at URL: s102550200048
OpenAlex ID: W2053148324
cites work: Q3097395
cites work: Connectivity of cages
cites work: Regular graphs with given girth pair
cites work: Q5785712
cites work: Q5461548
cites work: Cages—a survey
DOI: 10.1007/S102550200048
description: scientific article; zbMATH DE number 1885790