H-Decomposition of r-Graphs when H is an r-Graph with Exactly k Independent Edges

被引:0
作者
Xinmin Hou
Boyuan Liu
Hongliang Lu
机构
[1] University of Science and Technology of China,Key Laboratory of Wu Wen
[2] Xi’an Jiaotong University,Tsun Mathematics, School of Mathematical Sciences
来源
Graphs and Combinatorics | 2019年 / 35卷
关键词
Hypergraph; Decomposition; Independent edges;
D O I
暂无
中图分类号
学科分类号
摘要
Let ϕHr(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _H^r(n)$$\end{document} 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 ϕHr(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _H^r(n)$$\end{document} parts, of which every part either is a single edge or forms an r-graph isomorphic to H. The function ϕH2(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi ^2_H(n)$$\end{document} has been well studied in literature, but for the case r≥3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r\ge 3$$\end{document}, the problem of determining ϕHr(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _H^r(n)$$\end{document} is widely open. Sousa (Electron J Comb 17:R40, 2010) gave an asymptotic value of ϕHr(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _H^r(n)$$\end{document} when H is an r-graph with exactly 2 edges, and determined the exact value of ϕHr(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _H^r(n)$$\end{document} in some special cases. In this paper, we give the exact value of ϕHr(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _H^r(n)$$\end{document} when H is an r-graph with exactly 2 edges, which completes Sousa’s result, we further determine the exact value of ϕHr(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _H^r(n)$$\end{document} when H is an r-graph consisting of exactly k independent edges.
引用
收藏
页码:195 / 200
页数:5
相关论文
共 17 条
  • [1] Allen P(2014)An improved error term for minimum J. Comb. Theory Ser. B 108 92-101
  • [2] Böttcher J(1976)-decompotions of graphs Math. Proc. Camb. Philos. Soc. 79 19-24
  • [3] Person Y(1966)On complete subgraphs of different orders Canad. J. Math. 18 106-112
  • [4] Bollobás B(2013)The representation of a graph by set intersections J. Comb. Theory Ser. A 120 1068-1072
  • [5] Erdős P(2018)Improved bounds for Erdős matching conjecture J. Graph Theory 87 46-60
  • [6] Goodman AW(2018)Decompositions of graphs into Discrete Math. 341 126-137
  • [7] Pósa L(2007)-fans and single edges J. Comb. Theory Ser. B 97 1041-1055
  • [8] Frankl P(2010)Turán number and decomposition number of intersecting odd cycles Electron. J. Comb. 17 R40-undefined
  • [9] Hou X(undefined)Minimum undefined undefined undefined-undefined
  • [10] Qiu Y(undefined)-decompositions of graphs undefined undefined undefined-undefined