C₂k-saturated graphs with no short odd cycles

DOI10.1007/S00373-019-02054-XMaRDI QIDQ2334067zbMATH OpenOpenAlexFDO

Authors Craig Timmons

Publication date 6 November 2019

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.05772

zbMATH Keywords

cycle saturated graphcyclesgraph saturation

Mathematics Subject Classification ID

Paths and cycles (05C38)

Abstract: The saturation number of a graph $F$, written $extupsat(n,F)$, is the minimum number of edges in an $n$-vertex $F$-saturated graph. One of the earliest results on saturation numbers is due to ErdH{o}s, Hajnal, and Moon who determined $extupsat(n,K_r)$ for all $rgeq3$. Since then, saturation numbers of various graphs and hypergraphs have been studied. Motivated by Alon and Shikhelman's generalized Tur'an function, Kritschgau et. al. defined $extupsat(n,H,F)$ to be the minimum number of copies of $H$ in an $n$-vertex $F$-saturated graph. They proved, among other things, that $extupsat(n,C_3,C_{2k})=0$ for all $kgeq3$ and $ngeq2k+2$. We extend this result to all odd cycles by proving that for any odd integer $rgeq5$, $extupsat(n,C_r,C_{2k})=0$ for all $2kgeqr+5$ and $ngeq2kr$.

Recommendations

• Few \(H\) copies in \(F\)-saturated graphs
• Minimum C_k-saturated graphs
• Cycle-saturated graphs of minimum size
• Minimum C₅‐saturated graphs
• Minimizing the number of edges in \(\mathcal{C}_{\geq r} \)-saturated graphs

Cites work

• A generalized Turán problem and its applications
• A Problem in Graph Theory
• A survey of minimum saturated graphs
• All minimum \(C_{5}\)-saturated graphs
• Constructive upper bounds for cycle-saturated graphs of minimum size
• Cycle-saturated graphs of minimum size
• Cycle-saturated graphs with minimum number of edges
• Generalized Turán problems for even cycles
• Many \(T\) copies in \(H\)-free graphs
• Minimum C₅‐saturated graphs
• On the number of edges in a minimum \(C_6\)-saturated graph
• Saturated graphs with minimal number of edges

Cited in

(6)

• Minimizing the number of edges in \(\mathcal{C}_{\geq r} \)-saturated graphs
• The partite saturation number of spider
• Few \(H\) copies in \(F\)-saturated graphs
• Subgraph densities in a surface
• On the saturation spectrum of odd cycles
• Saturation numbers for linear forests P₅ P₄ tP₂

This page was built for publication: \(C_{2k}\)-saturated graphs with no short odd cycles

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