decompositions of Graphs into Fans and Single Edges

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

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 X(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 Özkahya 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 byFk, 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.

Original languageEnglish
Pages (from-to)400-411
Number of pages12
JournalJournal Of Graph Theory
Volume85
Issue number2
DOIs
Publication statusPublished - 1 Jun 2017

Keywords

  • extremal graph
  • fan graph
  • graph decomposition

Fingerprint Dive into the research topics of 'decompositions of Graphs into Fans and Single Edges'. Together they form a unique fingerprint.

  • Cite this