Upper bound on the size of subgraphs avoiding cycles of girth length in graphs
Abstract
A graph G is said to be H-free if it contains no copy of H. The generalized Turán number ex(G, H), a natural extension of the classical Turán number, is defined as the maximum number of edges in an H-free spanning subgraph of G. Although ex(G, H) has been extensively studied for various specific graphs G, such as hypercubes, complete transposition graphs, and doubled Johnson graphs, very few results are known for general graphs. For a graph G of girth g, let Cg denote the cycle of length g. In this paper, we investigate the generalized Turán number ex(G, Cg) for graphs G in which every edge is contained in a fixed number of g-cycles, and establish a general upper bound on it. This bound generalizes the classical results on hypercubes and provides a unified approach for general graphs. Furthermore, we apply this bound to derive explicit upper bounds for several specific graphs, including Kn,n,…,n, Kn× Kn, Cm× Cn, Sn, AGn, CTn and J(n;k,k+1).
Related
BibTeX
@misc{zhao2026upper,
title = {{Upper bound on the size of subgraphs avoiding cycles of girth length in graphs}},
author = {Shu-Li Zhao and Yu-Qi Li},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.08547},
eprint = {2611.08547},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.08547},
}
RIS
TY - UNPB
TI - Upper bound on the size of subgraphs avoiding cycles of girth length in graphs
AU - Shu-Li Zhao
AU - Yu-Qi Li
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.08547
UR - https://arxiv.org/abs/2611.08547
AB - A graph G is said to be H-free if it contains no copy of H. The generalized Turán number ex(G, H), a natural extension of the classical Turán number, is defined as the maximum number of edges in an H-free spanning subgraph of G. Although ex(G, H) has been extensively studied for various specific graphs G, such as hypercubes, complete transposition graphs, and doubled Johnson graphs, very few results are known for general graphs. For a graph G of girth g, let C_g denote the cycle of length g. In this paper, we investigate the generalized Turán number ex(G, C_g) for graphs G in which every edge is contained in a fixed number of g-cycles, and establish a general upper bound on it. This bound generalizes the classical results on hypercubes and provides a unified approach for general graphs. Furthermore, we apply this bound to derive explicit upper bounds for several specific graphs, including K_n,n,…,n, K_n× K_n, C_m× C_n, S_n, AG_n, CT_n and J(n;k,k+1).
ER -