Trinque problem: covering complete graphs by plane degree-bounded hypergraphs

详细信息    查看全文

• 作者：Clément Charpentier ; Sylvain Gravier…
• 关键词：Plane hypergraph ; Edge covering ; Complete graphs ; Edge partition
• 刊名：Journal of Combinatorial Optimization
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：33
• 期：2
• 页码：543-550
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Theory of Computation; Optimization; Operation Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2886
• 卷排序：33

文摘

Let \(K_n\) be a complete graph drawn on the plane with every vertex incident to the infinite face. For any integers i and d, we define the (i, d)-Trinque Number of \(K_n\), denoted by \({\mathcal {T}}^d_{i}(K_n)\), as the smallest integer k such that there is an edge-covering of \(K_n\) by k “plane” hypergraphs of degree at most d and size of edge bounded by i. We compute this number for graphs (that is \(i=2\)) and gives some bounds for general hypergraphs.