Research articles
ScienceAsia 50 (2024):ID 2024003 1-7 |doi:
10.2306/scienceasia1513-1874.2024.003
New sufficient conditions for Hamiltonian, pancyclic and
edge-Hamilton graphs
Fayun Caoa,*, Han Renb
ABSTRACT: The decycling number ?(G) of a graph G is the smallest number of vertices whose deletion yields a forest.
Bau and Beineke proved that ?(G) ? ?(G) + 1 for every graph G, where ?(G) is the connectivity of G (Australas J
Combin, 25:285-298, 2002). In this paper, we consider graphs with ?(G) = ?(G)+1 and establish sufficient conditions
for such graphs to be Hamiltonian, pancyclic and edge-Hamilton, respectively. To our knowledge, this is the first result
studying Hamilton problem in terms of decycling number. It is well-known that determining the decycling number of
a graph is equivalent to finding the greatest order of an induced forest and some sufficient conditions for Hamiltonian
graphs are also sufficient for the existence of completely independent spanning trees. This paper may provide a new
condition implying completely independent spanning trees.
Download PDF
11 Downloads 641 Views
| a |
Department of Mathematics, Shanghai Business School, Shanghai 200235 China |
| b |
School of Mathematics and Science, East China Normal University, Shanghai 200241 China |
* Corresponding author, E-mail: caofayun@126.com
Received 3 Nov 2022, Accepted 18 Jun 2023
|
