Implicit degree condition restricted to essential independent sets for Hamiltonian cycles
Indian Journal of Pure and Applied Mathematics - Trang 1-7 - 2023
Tóm tắt
A cycle of a graph G is Hamiltonian if it visits every vertex of G exactly once. A graph is Hamiltonian if it has a Hamiltonian cycle. The problem of determining whether a graph is Hamiltonian is known to be NP-complete. A subset S of V(G) is called an essential independent set of G if S is an independent set and contains two distinct vertices u and v with a common neighbor. In 1989, Zhu, Li and Deng introduced the definitions of the first implicit degree and the second implicit degree of a vertex v in a graph G, denoted by
$$id_1(v)$$
and
$$id_2(v)$$
, respectively. In this paper, we show that a k-connected (
$$k\ge 2$$
) graph G of order
$$n\ge 3$$
is Hamiltonian if
$$\max \{id_1(v): v\in S\}\ge n/2$$
for every essential independent set S of order k and the bound “n/2” is tight, which generalizes the result due to Chen et al. [Essential Independent Sets and Hamiltonian Cycles, J. Graph Theory, 21 (1996) 243–250.].
Tài liệu tham khảo
J.A. Bondy, Large cycles in graphs, Discrete Math., 1 (1971) 121–132.
J.A. Bondy, Longest paths and cycles in graphs of high degree, Research Report CORR 80-16, Univ. of Waterloo, Waterloo, Ont. (1980).
J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London, 1976.
J. Cai, H. Li and Y. Zhang, An implicit degree condition for k-connected 2-heavy graphs to be Hamiltonian, Inform. Process. Lett., 134 (2018) 9–13.
J. Cai and L. Wang, A Generalization of Implicit Ore-condition for Hamiltonicity of k-connected Graphs, Acta Math. Appl. Sin-E, 36 (2020) 620–626.
G. Chen, Y. Egawa, X. Liu and A. Saito, Essential Independent Sets and Hamiltonian Cycles, J. Graph Theory, 21 (1996) 243–250.
V. Chvátal and P. Erdös, A note on Hamiltonian circuits, Discrete Math., 2 (1972) 111–113.
G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc., 2 (1952), 69–81.
G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B, 37 (1984) 221–227.
M. Hasan, M. Kaykobadb, Y. Lee and S. Lee, A comprehensive analysis of degree based condition for Hamiltonian cycles, Theor. Comput. Sci., 411 (2010) 285–287.
H. Li, W. Ning and J. Cai, An implicit degree condition for cyclability in graphs, FAW-AAIM 2011, LNCS, 6681 (2011) 82–89.
H. Li, W. Ning and J. Cai, An implicit degree condition for Hamiltonian graphs, Discrete Math., 312 (2012) 2190–2196.
L. Mehedy, M. Hasan and M. Kaykobad, An Improved Degree Based Condition for Hamiltonian Cycles, Inform. Process. Lett., 102 (2007) 108–112.
O. Ore, Note on Hamilton circuits, Amer. Math. Mon., 67 (1960) 55.
M. Rahman and M. Kaykobad, On Hamiltonian cycles and Hamiltonian paths, Inform. Process. Lett., 94 (2005) 37–41.
K. Zhao and R. Gould, A note on the Song–Zhang theorem for Hamiltonian graphs, Colloq. Math., 120 (2010) 63–75.
K. Zhao, H. Lai and Y. Shao, New sufficient condition for Hamiltonian graphs, Appl. Math. Lett., 20 (2007) 116–122.
Y. Zhu, H. Li and X. Deng, Implicit-degrees and circumferences, Graphs Combin., 5 (1989) 283–290.