Decomposition of graphs into (k,r)-fans and single edges

DOI10.1002/JGT.22139MaRDI QIDQ4604014zbMATH OpenOpenAlexFDO

Authors Yu Qiu, Boyuan Liu, Xinmin Hou

Publication date 23 February 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.00811

zbMATH Keywords

extremal graphdecompositionsfans

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $phi(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 $phi(n,H)$ parts, of which every part either is a single edge or forms a graph isomorphic to $H$. Pikhurko and Sousa conjectured that $phi(n,H)=ex(n,H)$ for $chi(H)geqs3$ and all sufficiently large $n$, where $ex(n,H)$ denotes the maximum number of edges of graphs on $n$ vertices that does 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$ which intersect in exactly one common vertex. In this paper, we verify Pikhurko and Sousa's conjecture for $(k,r)$-fans. The result also generalizes a result of Liu and Sousa.

Recommendations

• Decompositions of graphs into fans and single edges
• Minimum \(H\)-decompositions of graphs: edge-critical case
• \(H\)-decomposition of \(r\)-graphs when \(H\) is an \(r\)-graph with exactly \(k\) independent edges
• An improved error term for minimum H-decompositions of graphs
• Spectral extremal graphs for intersecting cliques

Cites work

• scientific article; zbMATH DE number 6093217 (Why is no real title available?)
• An improved error term for minimum H-decompositions of graphs
• Decomposition of graphs into cycles of length seven and single edges.
• Decompositions of graphs into 5-cycles and other small graphs
• Decompositions of graphs into fans and single edges
• Degrees and matchings
• Extremal graphs for intersecting cliques
• Minimum \(H\)-decompositions of graphs
• Minimum \(H\)-decompositions of graphs: edge-critical case
• On complete subgraphs of different orders
• The Representation of a Graph by Set Intersections

Cited in

(5)

• Decomposing uniform hypergraphs into uniform hypertrees and single edges
• \(H\)-decomposition of \(r\)-graphs when \(H\) is an \(r\)-graph with exactly \(k\) independent edges
• Minimum \(H\)-decompositions of graphs: edge-critical case
• Decompositions of graphs into fans and single edges
• Extremal graphs for the suspension of edge-critical graphs

This page was built for publication: Decomposition of graphs into \((k,r)\)-fans and single edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604014)