Decomposing uniform hypergraphs into uniform hypertrees and single edges

被引:0
|
作者
Kang, Liying [1 ]
Ni, Zhenyu [1 ]
Shan, Erfang [2 ]
机构
[1] Shanghai Univ, Dept Math, Shanghai 200444, Peoples R China
[2] Shanghai Univ, Sch Management, Shanghai 200444, Peoples R China
基金
中国国家自然科学基金;
关键词
Hypergraph; Hypertree; Decomposition; MINIMUM H-DECOMPOSITIONS; GRAPHS;
D O I
10.1016/j.disc.2021.112454
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given two r-uniform hypergraphs 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 hypergraph isomorphic to H. Let phi(r)(n, H) be the smallest integer such that any r-uniform hypergraph G of order n admits an H-decomposition with at most phi(r)(n, H) parts. In this paper we determine the exact value of phi(r)(n, H) when H is an arbitrary r-uniform hypertree with t edges. (C) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页数:9
相关论文
共 50 条
  • [41] On distance spectral radius of uniform hypergraphs
    Lin, Hongying
    Zhou, Bo
    Li, Yaduan
    LINEAR & MULTILINEAR ALGEBRA, 2018, 66 (03) : 497 - 513
  • [42] On Lagrangians of r-uniform hypergraphs
    Peng, Yuejian
    Tang, Qingsong
    Zhao, Cheng
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 30 (03) : 812 - 825
  • [43] On the VC-dimension of uniform hypergraphs
    Mubayi, Dhruv
    Zhao, Yi
    JOURNAL OF ALGEBRAIC COMBINATORICS, 2007, 25 (01) : 101 - 110
  • [44] On hamiltonian chain saturated uniform hypergraphs
    Dudek, Aneta
    Zak, Andrzej
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2012, 14 (01) : 21 - 28
  • [45] Maximally connected p-partite uniform hypergraphs
    Shan, Erfang
    Zhao, Jing
    Kang, Liying
    DISCRETE APPLIED MATHEMATICS, 2019, 264 : 188 - 195
  • [46] Mixed covering arrays on 3-uniform hypergraphs
    Akhtar, Yasmeen
    Maity, Soumen
    DISCRETE APPLIED MATHEMATICS, 2017, 232 : 8 - 22
  • [47] On the Turán Density of Uniform Hypergraphs
    An Chang
    Guo-rong Gao
    Acta Mathematicae Applicatae Sinica, English Series, 2023, 39 : 638 - 646
  • [48] THE BOLLOBAS SCOTT CONJECTURE FOR 4-UNIFORM HYPERGRAPHS
    Hou, Jianfeng
    Wu, Shufei
    Zeng, Qinghou
    Zhu, Wenxing
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (01) : 505 - 521
  • [49] The existence of panchromatic colourings for uniform hypergraphs
    Shabanov, D. A.
    SBORNIK MATHEMATICS, 2010, 201 (3-4) : 607 - 630
  • [50] Prime 3-Uniform Hypergraphs
    Abderrahim Boussaïri
    Brahim Chergui
    Pierre Ille
    Mohamed Zaidi
    Graphs and Combinatorics, 2021, 37 : 2737 - 2760