H-Decomposition of r-graphs when H is an r-graph with exactly k independent edges

2017/10/15 by Xinmin Hou, Boyuan Liu, Hou, Xinmin +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1710.05347

openalex publication_date 2017/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let ϕ_H^r(n) be the smallest integer such that, for all r-graphs G on n vertices, the edge set E(G) can be partitioned into at most ϕ_H^r(n) parts, of which every part either is a single edge or forms an r-graph isomorphic to H. The function ϕ²_H(n) has been well studied in literature, but for the case r≥ 3, the problem that determining the value of ϕ_H^r(n) is widely open. Sousa (2010) gave an asymptotic value of ϕ_H^r(n) when H is an r-graph with exactly 2 edges, and determined the exact value of ϕ_H^r(n) in some special cases. In this paper, we first give the exact value of ϕ_H^r(n) when H is an r-graph with exactly 2 edges, which improves Sousa's result. Second we determine the exact value of ϕ_H^r(n) when H is an r-graph consisting of exactly k independent edges.

Citations

• The Representation of a Graph by Set Intersections

Related

• Forbidden subgraphs and complete partitions
• An improved error term for minimum H-decompositions of graphs
• Decomposing the Complete r-Graph
• Decomposition of Graphs into (k,r)-Fans and Single Edges
• H-Decompositions