Decomposition of Graphs into (k,r)‐Fans and Single Edges期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Decomposition of Graphs into (k,r)‐Fans and Single Edges

Abstract:	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) ⩾ 3$ and all sufficiently large n, where $ex (n, H)$ denotes the maximum number of edges of graphs on n vertices that do not contain H as a subgraph. A $(k, r)$ ‐fan is a graph on $(r - 1) k + 1$ vertices consisting of k cliques of order r that intersect in exactly one common vertex. In this article, we verify Pikhurko and Sousa's conjecture for $(k, r)$ ‐fans. The result also generalizes a result of Liu and Sousa.

Keywords:	extremal graph decompositions fans