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

DOI10.1002/JGT.22139zbMATH Open1380.05161arXiv1510.00811OpenAlexW2964080531MaRDI QIDQ4604014FDOQ4604014

Authors: Yu Qiu, Boyuan Liu, Xinmin Hou 

Publication date: 23 February 2018

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

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.

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

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

zbMATH Keywords

extremal graphdecompositionsfans

Mathematics Subject Classification ID

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

Cites Work

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

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)