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 ï¾ź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 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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1002/jgt.22069 | Journal of Graph Theory |
Keywords | Field | DocType |
fan graph,graph decomposition,extremal graph | Topology,Discrete mathematics,Combinatorics,Vertex-transitive graph,Graph power,Cubic graph,Cycle graph,Factor-critical graph,Graph minor,Symmetric graph,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
85 | 2 | 0364-9024 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Henry Liu | 1 | 16 | 5.35 |
Teresa Sousa | 2 | 9 | 2.72 |