Extremal even-cycle-free subgraphs of the k-ary n-cube
Abstract
A graph is said to be H-free if it contains no subgraph isomorphic to 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. For any integer ℓ≥ 2, let C2ℓ denote the even cycle of length 2ℓ. So far, extensive studies of the generalized Turán number for the hypercube Qn have been conducted. The k-ary n-cube is an important family of graphs with many favorable properties, such as regularity and vertex-transitivity. It generalizes the hypercube and reduces to the hypercube when k=2. In this paper, we investigate the generalized Turán number ex(Qkn, C2ℓ) of Qkn for all even integers k≥ 4 and integers ℓ≥ 2, generalizing the result for Qn [J. Graph Theory 16 (1992) 273-286] from k=2 to k≥ 4.
Related
BibTeX
@misc{zhao2026extremal,
title = {{Extremal even-cycle-free subgraphs of the $k$-ary $n$-cube}},
author = {Shu-Li Zhao and Yu-Qi Li},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05433},
eprint = {2611.05433},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05433},
}
RIS
TY - UNPB
TI - Extremal even-cycle-free subgraphs of the k-ary n-cube
AU - Shu-Li Zhao
AU - Yu-Qi Li
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05433
UR - https://arxiv.org/abs/2611.05433
AB - A graph is said to be H-free if it contains no subgraph isomorphic to 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. For any integer ℓ≥ 2, let C_2ℓ denote the even cycle of length 2ℓ. So far, extensive studies of the generalized Turán number for the hypercube Q_n have been conducted. The k-ary n-cube is an important family of graphs with many favorable properties, such as regularity and vertex-transitivity. It generalizes the hypercube and reduces to the hypercube when k=2. In this paper, we investigate the generalized Turán number ex(Q^k_n, C_2ℓ) of Q^k_n for all even integers k≥ 4 and integers ℓ≥ 2, generalizing the result for Q_n [J. Graph Theory 16 (1992) 273-286] from k=2 to k≥ 4.
ER -