Dense graphs with cycle neighborhoods

DOI10.1006/JCTB.1995.1020MaRDI QIDQ1892847zbMATH OpenOpenAlexFDO

Authors Tibor Szabó, Ákos Seress

Publication date 2 July 1995

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1995.1020

zbMATH Keywords

clean triangulationcyclecycle neighborhoodsdense graphsextremal graphneighborhood

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Review text

For all \(\varepsilon > 0\), we construct graphs with \(n\) vertices and \(> n^{2-\varepsilon}\) edges, for arbitrarily large \(n\), such that the neighborhood of each vertex is a cycle. This result is asymptotically best possible.

Recommendations

• Cycle factors in dense graphs
• Publication:4726282
• New families of graphs without short cycles and large size
• Neighborhood unions and the cycle cover number of a graph

Cited in

(8)

• Cycle factors in dense graphs
• Dense periodicity on graphs
• On extremal sizes of locally \(k\)-tree graphs.
• Cycles of Given Size in a Dense Graph
• scientific article; zbMATH DE number 150463 (Why is no real title available?)
• scientific article; zbMATH DE number 798648 (Why is no real title available?)
• STACS 2004
• Markov bases of binary graph models of \(K_{4}\)-minor free graphs

This page was built for publication: Dense graphs with cycle neighborhoods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892847)