| Home  | About ScienceAsia  | Publication charge  | Advertise with us  | Subscription for printed version  | Contact us  
Editorial Board
Journal Policy
Instructions for Authors
Online submission
Author Login
Reviewer Login
Volume 50 Number 4
Volume 50 Number 3
Volume 50 Number 2
Volume 50 Number 1
Volume 49 Number 6
Volume 49 Number 5
Earlier issues
Volume 49 Number 3


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 556 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