Xu Guangjun, Sun Qiang, Liang Zuosong
School of Mathematics, Zunyi Normal University, Zunyi, Guizhou, China.
School of Mathematical Science, Yangzhou University, Yangzhou, China.
Comput Intell Neurosci. 2022 Apr 28;2022:5837405. doi: 10.1155/2022/5837405. eCollection 2022.
A 4-tuple (, , , ) in a graph is a 3-arc if each of (, , ) and (, , ) is a path. The 3-arc graph of is the graph with vertex set all arcs of and edge set containing all edges joining and whenever (, , , ) is a 3-arc of . A Hamilton cycle is a closed path meeting each vertex of a graph. A graph including a Hamilton cycle is called Hamiltonian and has a Hamiltonian decomposition provided its edge set admits a partition into disjoint Hamilton cycles (possibly with a single perfect matching). The current paper proves that every connected 3-arc graph consists of more than one Hamilton cycle. Since the 3-arc graph of a cubic graph is 4-regular, it further proves that each 3-arc graph of a cubic graph in a certain family has a Hamiltonian decomposition.
图中的一个四元组(, ,, )若满足(, ,, )和(, ,, )均为路径，则它是一条3 - 弧。图的3 - 弧图是这样一个图，其顶点集为图的所有弧，边集包含所有连接和的边，当(, ,, , )是图的一条3 - 弧时。哈密顿圈是一个与图的每个顶点都相交的闭路径。包含哈密顿圈的图称为哈密顿图，并且如果图的边集允许划分为不相交的哈密顿圈（可能带有一个完美匹配），则称该图具有哈密顿分解。本文证明了每个连通的3 - 弧图都由多个哈密顿圈组成。由于三次图的3 - 弧图是4 - 正则的，进一步证明了某一族三次图的每个3 - 弧图都具有哈密顿分解。
