Properties of certain families of \(2k\)-cycle-free graphs
type: Item
instance of: scholarly article
title: Properties of certain families of \(2k\)-cycle-free graphs
zbMATH Open document ID: 0803.05028
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-01-02T00:00:00Z
review text: Where, for a fixed family \(\mathcal F\) of graphs, and a sequence \({\mathcal H}= \{H_ i\}_{i\geq 1}\) of \({\mathcal F}\)-free graphs with \(\{v_ i= v(H_ i)\}_{i\geq 1}\) increasing, there exists a minimum \(r\) such that \(e(H_ i)= (\lambda+ o(1)) v_ i^ r\) as \(i\to \infty\), \(r= r({\mathcal H})\) is called the magnitude of \(\mathcal H\); where a maximum \(\lambda\) exists with this property, it is called the constant of \(\mathcal H\), and denoted by \(\lambda({\mathcal H})\). All sequences \(\mathcal H\) of extremal graphs (such that \(e(H_ i)=\text{ex}(v_ i,{\mathcal F})\)) have the same magnitude and constant (where these exist), denoted by \(r_{{\mathcal F}}\), \(\lambda_{{\mathcal F}}\) respectively. \(\mathcal H\) is magnitude extremal if, while it need not be extremal, \(r({\mathcal H})= r_{{\mathcal F}}\). In the present paper \({\mathcal F}= \{C_{2k}\}\). The authors begin with the observation that, wherever \(r_{\{C_{2k}\}}\) is known, there exists a magnitude extremal sequence of ``high'' girth bipartite graphs. ``In this note we show that while \(\{C_{2k}\}\)-magnitude extremality can be achieved with (sequences of) bipartite graphs of high girth, ordinary extremality cannot.'' ``Theorem. Let \(k\geq 3\), and let \(\mathcal G\) be a family of \(2k\)-cycle-free graphs with magnitude \(r> 1\) and constant \(\lambda> 0\), the members of which are bipartite graphs of girth at least \(2k+2\). Then, for any \(t\), \(2\leq t\leq k-1\), there exists a family \(\widetilde{{\mathcal G}_ t}\) of \(2k\)-cycle-free graphs with magnitude \(r\) and constant \(\widetilde\lambda \geq t(2/(t+1))^ r\lambda> \lambda\), all of whose members are bipartite and contain each of the cycles \(C_ 4,C_ 6,\dots,C_{2t}\), and none of the cycles \(C_{2t+ 2},\dots,C_{2k}\). Consequently, any family of \(\{C_{2k}\}\)-extremal graphs must consist (with finitely many exceptions) either of graphs that are non-bipartite or (of graphs that) have girth at most \(2k- 2\).'' ``Recently, t…
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 562410
zbMATH Keywords: cycle-free graphs
zbMATH Keywords: extremal graphs
zbMATH Keywords: magnitude
zbMATH Keywords: constant
zbMATH Keywords: extremal sequence
zbMATH Keywords: bipartite graphs
zbMATH Keywords: girth
zbMATH Keywords: lower bound
Wikidata QID: Q56698341
author: Felix Lazebnik
author: V. A. Ustimenko
author: Andrew J. Woldar
reviewed by: William G. Brown
MaRDI profile type: Publication
full work available at URL: jctb.1994.1020
OpenAlex ID: W2093219044
DOI: 10.1006/JCTB.1994.1020
description: scientific article; zbMATH DE number 562410