2016/10/04 by Hou, Xinmin, Qiu, Yu, Liu, Boyuan · 2 citations
#05C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1610.00815
An extremal graph for a given graph H is a graph on n vertices with maximum number of edges that does not contain H as a subgraph. Let s,t be integers and let Hs,t be a graph consisting of s triangles and t cycles of odd lengths at least 5 which intersect in exactly one common vertex. Erdős et al. (1995) determined the extremal graphs for Hs,0. Recently, Hou et al. (2016) determined the extremal graphs for H0,t, where the t cycles have the same odd length q with q≥ 5. In this paper, we further determine the extremal graphs for Hs,t with s≥ 0 and t≥ 1. Let ϕ(n,H) be the largest integer such that, for all graphs G on n vertices, the edge set E(G) can be partitioned into at most ϕ(n, H) parts, of which every part either is a single edge or forms a graph isomorphic to H. Pikhurko and Sousa conjectured that ϕ(n,H)=\ex(n,H) for χ(H)\geqs3 and all sufficiently large n. Liu and Sousa (2015) verified the conjecture for Hs,0. In this paper, we further verify Pikhurko and Sousa's conjecture for Hs,t with s≥ 0 and t≥ 1.