完全3-均匀超图分解为5-圈
62 浏览量
更新于2024-08-27
收藏 248KB PDF 举报
"Decomposing Complete 3-uniform Hypergraph into 5-cycles"
这篇研究论文主要探讨了将完全3-均匀超图分解为5-循环的问题。在图论中，超图是一种扩展了传统图概念的结构，其中边可以连接任意数量的顶点，而不仅仅是两个。3-均匀超图是指每条边都连接着三个顶点的超图。5-循环则是一个包含5个顶点和5条边的简单闭合路径。
关键词包括：均匀超图、5-循环和周期分解。论文涉及了Katona-Kierstead对超图中哈密顿周期的定义，以及Bailey-Stevens和Meszka-Rosa关于如何将完全k-均匀超图分解为哈密顿周期的研究。哈密顿周期是图论中的一个重要概念，指的是在图中找到一条经过每个顶点恰好一次的闭合路径。
对于模6同余2、4或5的n值，作者设计了一种基于边划分的算法来分解完全3-均匀超图（记为K_n^3）为哈密顿周期。具体来说，他们展示了一个当n小于等于17且满足适配条件的分解方法，将K_n^3分解为5-循环。这里的适配条件可能涉及到n与边的数量之间的关系。
论文还提到了Jirimutu和Wang提出的边划分和周期序列方法，并利用这种方法找到了将K_{20}^3分解为5-循环的具体分解。尽管如此，对于一般情况下的n值，将完全3-均匀超图分解为5-循环的问题仍然是一个开放问题，即尚未找到普适的解决方案。
这篇论文贡献了新的算法和技术，用于解决特定条件下超图的周期性结构问题，这在理论计算机科学和图论领域具有重要意义，因为这类问题对于理解和设计高效的图算法至关重要。此外，它也对进一步探索超图的结构特性提供了新的视角和工具。
Decomposing Complete 3-uniform Hypergraph into 5-cycles
Guanru Li
1, a
, Yiming Lei
1,a
and Jirimutu
1,b *
1
College of Mathematics, Institute of Discrete Mathematics of Inner Mongolia University for the
Nationalities, Tongliao
a
email200101@126.com,
b
jrmt@sina.com
Keywords: Uniform hypergraph; 5-cycle; Cycle decomposition
Abstract. About the Katona-Kierstead definition of a Hamiltonian cycles in a uniform hypergraph, a
decomposition of complete
k
-uniform hypergraph
( )
k
n
K
into Hamiltonian cycles studied by
Bailey-Stevens and Meszka-Rosa. For
2,4,5
n
≡
(mod 6), we design algorithm for decomposing the
complete 3-uniform hypergraphs into Hamiltonian cycles by using the method of edge-partition. A
decomposition of
(3)
n
K
into 5-cycles has been presented for all admissible
17
n
≤
, and for all
4 1
m
n
= +
,
m
is a positive integer. In general, the existence of a decomposition into 5-cycles remains
open. In this paper, we use the method of edge-partition and cycle sequence proposed by Jirimutu and
Wang. We find a decomposition of
(3)
20
K
into 5-cycles.
Introduction
Many papers studied the two different definitions of a Hamiltonian cycle in [1] and [3], which
are due to Katona-Kierstead, Wang and Lee respectively. In fact, two different definitions of a
Hamiltonian cycle are the same. A decomposition of the complete
k
-uniform hypergraphs into
Hamiltonian cycles has been considered in [2-9]. In [2], Hamiltonian decompositions of
(3)
n
K
for all
admissible
32
n
≤
has been resolved. Recently, by programming, using the method of edge-partition
and cycle sequence, we have obtained some results for all admissible
32 46
n
< ≤
and
43
n
≠
in [10].
In [2], the problem of decomposing the complete 3- uniform hypergraph into 5-cycles is open.
Meszka and Rosa have introduced a necessary condition for the existence of such a decomposition is
that
1, 2,5, 7,10
n
≡
or 11 (mod 15). A decomposition of
(3)
n
K
into 5- cycles exists for all admissible
17
n
≤
, for all
4 1
m
n
= +
,
m
is a positive integer. In this paper, we find a decomposition of
(3)
20
K
into
5-cycles.
Preliminaries
A hypergraph
( , )
H V E
=
consists of a finite set
V
of vertices with a family
E
of subsets of
V
,
called hyperedges (or simply edges). If each (hyper)edge has size
k
, we say that
H
is a
k
-uniform
hypergraph. In particular, the complete
k
-uniform hypergraph on
n
vertices has all
k
-subsets of
{1, 2, , }
n
as edges, denoted this by
( )
k
n
K
. The (hyper)edges of
(3)
n
K
is denoted by
(3)
( )
n
K
ε
.
Definition 1.1 Let
( , )
H V E
=
be a
k
- uniform hypergraph. A
l
-cycle in
H
is a cyclic sequence
0 1 1
( , , , )
l
v v v
−
of
V
where
3 1
k l
≤ < −
such that each consecutive
k
-tuple of vertices is an edge of
E
.
Definition 1.2
A
l
-cycle decomposition of
H
is a partition of the set of (hyper)edges of
H
into
mutually-disjoint
l
-cycles.
We introduce the method of edge-partition and cycle-model in [5].
Applied Mechanics and Materials Vols. 672-674 (2014) pp 1935-1939 Submitted: 25.07.2014
© (2014) Trans Tech Publications, Switzerland Accepted: 09.08.2014
doi:10.4028/www.scientific.net/AMM.672-674.1935
All rights reserved. No part of contents of this paper may be reproduced or transmitted in any form or by any means without the written permission of TTP,
www.ttp.net. (ID: 1.180.181.194-04/10/14,13:23:33)
下载后可阅读完整内容，剩余4页未读，立即下载
2019-10-25 上传
888 浏览量
2022-07-15 上传
2021-05-09 上传
159 浏览量
2010-01-07 上传
2024-07-11 上传
2021-02-05 上传
132 浏览量
2021-04-22 上传
weixin_38642897
- 粉丝: 3
我的内容管理
展开
最新资源
- Zabbix与Grafana服务器搭建源代码包指南
- React应用开发指南：掌握Create React App
- Netlify静态站点部署教程：从创建到部署
- Rust语言版LeetCode问题解答集
- TensorFlow实现的EAST文本检测器在Python中的高效应用
- 构建电子商务应用：React与现代技术栈实战指南
- 企业级网页模板设计：数字生活与创新美学
- LVM在Linux系统中的应用与管理
- Android自定义相机实现拍照与对焦功能教程
- GitTest1项目核心功能解析与应用
- pymde-0.1.13 Python库安装指南及资源下载
- Python打造LoL统计数据API：概念验证与应用
- 绿色木霉原生质体制备及转化技术要点解析
- webtrees-branch-statistics模块：家谱代际统计功能介绍
- Accitro: 开源级别与排名系统bot的discord.js实现
- MiniOrm-for-Android：高效便捷的Android ORM框架
