Extremal problems involving vertices and edges on odd cycles
type: Item
instance of: scholarly article
title: Extremal problems involving vertices and edges on odd cycles
zbMATH Open document ID: 0767.05056
DOI: 10.1016/0012-365X(92)90586-5
author: Ralph Faudree
author: Cecil Rousseau
author: P. Erdős
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: Let \(G\) be a graph on \(n\) vertices and with \(\lfloor n^2/4\rfloor+1\) or more edges. The authors investigate the minimum of the number of vertices and edges of \(G\) which are on triangles and, more generally, cycles of length \(2k+1\). They also conjecture that if \(k\geq 2\) then at least \(2n^2/9-O(n)\) edges of \(G\) are on cycles of length \(2k+1\).
reviewed by: J.Sedláček
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 89886
zbMATH Keywords: extremal problems
zbMATH Keywords: odd cycles
zbMATH Keywords: Turán graph
MaRDI profile type: Publication
cites work: Graphs with unavoidable subgraphs with large degrees
cites work: Q3818315
cites work: Q4200251
cites work: On a theorem of Rademacher-Turán
cites work: On maximal paths and circuits of graphs
cites work: Degree sum for a triangle in a graph
cites work: An extremal problem for paths in bipartite graphs
cites work: Sufficient Conditions for Circuits in Graphs†
description: scientific article; zbMATH DE number 89886