Decompositions of Graphs into Fans and Single Edges
2017
Given two graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let φ(n,H) be the smallest number ϕ such that any graph G of order n admits an H-decomposition with at most ϕ parts. 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 in a graph on n vertices not containing H as a subgraph. Their conjecture has been verified by Ozkahya and Person for all edge-critical graphs H. In this article, the conjecture is verified for the k-fan graph. The k-fan graph, denoted by Fk, is the graph on 2k+1 vertices consisting of k triangles that intersect in exactly one common vertex called the center of the k-fan.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
10
References
6
Citations
NaN
KQI