2019/07/05 by Mengyu Cao, Cao, Mengyu, Benjian Lv +3 · 1 citation
Mathematics · Computer Science · Engineering · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1907.02725
The generalized Turán number \rm ex(G,H) is the maximum number of edges in an H-free subgraph of a graph G. It is an important extension of the classical Turán number \rm ex(n,H), which is the maximum number of edges in a graph with n vertices that does not contain H as a subgraph. In this paper, we consider the maximum number of edges in an even-cycle-free subgraph of the doubled Johnson graphs J(n;k,k+1), which are bipartite subgraphs of hypercube graphs. We give an upper bound for \rm ex(J(n;k,k+1),C2r) with any fixed k∈ℤ+ and any n∈ℤ+ with n≥ 2k+1. We also give an upper bound for \rm ex(J(2k+1;k,k+1),C2r) with any k∈ℤ+, where J(2k+1;k,k+1) is known as doubled Odd graph \widetildeOk+1. This bound induces that the number of edges in any C2r-free subgraph of \widetildeOk+1 is o(e(\widetildeOk+1)) for r≥ 6, which also implies a Ramsey-type result.