On Hamiltonian Decomposition Problem of 3-Arc Graphs
Open Access
- 28 April 2022
- journal article
- research article
- Published by Wiley in Computational Intelligence and Neuroscience
- Vol. 2022, 1-6
Abstract
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.Keywords
Funding Information
- National Natural Science Foundation of China (11661084, 11801494, 11971196, [2017]1201, [2020] 093, ZR2021MA012)
- Science and Technology Foundation of Guizhou Province (11661084, 11801494, 11971196, [2017]1201, [2020] 093, ZR2021MA012)
- Growth Project of Young Scientific and Technological Talents in Colleges and Universities of Guizhou Province (11661084, 11801494, 11971196, [2017]1201, [2020] 093, ZR2021MA012)
- Natural Science Foundation of Shandong Province (11661084, 11801494, 11971196, [2017]1201, [2020] 093, ZR2021MA012)
This publication has 8 references indexed in Scilit:
- Hamilton-Connected Mycielski Graphs∗Discrete Dynamics in Nature and Society, 2021
- FINITE SYMMETRIC GRAPHS WITH 2-ARC-TRANSITIVE QUOTIENTS: AFFINE CASEBulletin of the Australian Mathematical Society, 2015
- On the connectivity and restricted edge-connectivity of 3-arc graphsDiscrete Applied Mathematics, 2014
- Hamiltonicity of 3-Arc GraphsGraphs and Combinatorics, 2013
- Graph Theory2008
- Advances on the Hamiltonian Problem - A SurveyGraphs and Combinatorics, 2003
- A class of finite symmetric graphs with 2-arc transitive quotientsMathematical Proceedings of the Cambridge Philosophical Society, 2000
- Counting 1-Factors in Regular Bipartite GraphsJournal of Combinatorial Theory, Series B, 1998