Isolated Toughness and k -Hamiltonian [ a, b ]-factors
- PDF / 136,022 Bytes
- 6 Pages / 612 x 792 pts (letter) Page_size
- 27 Downloads / 202 Views
Acta Mathemacae Applicatae Sinica, English Series The Editorial Office of AMAS & Springer-Verlag GmbH Germany 2020
Isolated Toughness and k-Hamiltonian [a, b]-factors Zhi-ren SUN1 , Si-zhong ZHOU2,† 1 School
of Mathematical Sciences, Nanjing Normal University, Nanjing 210046, China
(E-mail: [email protected]) 2 School of Science, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang 212003, China (E-mail: zsz [email protected])
Abstract
Let a, b and k be nonnegative integers with a ≥ 2 and b ≥ a(k + 1) + 2. A graph G is called a
k-Hamiltonian graph if after deleting any k vertices of G the remaining graph of G has a Hamiltonian cycle. A graph G is said to have a k-Hamiltonian [a, b]-factor if after deleting any k vertices of G the remaining graph of G admits a Hamiltonian [a, b]-factor. Let G is a k-Hamiltonian graph of order n with n ≥ a + k + 2. In this paper, a(k+1) it is proved that G contains a k-Hamiltonian [a, b]-factor if δ(G) ≥ a + k and δ(G) ≥ I(G) ≥ a − 1 + b−2 . Keywords
isolated toughness; k-Hamiltonian graph; k-Hamiltonian [a, b]-factor
2000 MR Subject Classification
1
05C70; 05C45
Introduction
We begin with notations and definitions. In this paper, we consider only finite undirected graphs which do not contain loops and multiple edges. Let G be a graph. The vertex set and edge set of a graph G are denoted by V (G) and E(G), respectively. For any x ∈ V (G), we denote by dG (x) the degree of∪x in G, and by NG (x) the set of vertices adjacent to x in G. For NG (x), G[X] denotes the subgraph of a graph G induced by any X ⊆ V (G), NG (X) = x∈X
X and G − X denotes the subgraph of a graph G induced by V (G) \ X. The minimum degree and the maximum degree of a graph G are denoted by δ(G) and ∆(G), respectively. We use i(G) to denote the number of isolated vertices in a graph G. The isolated toughness I(G) of a graph G was first introduced by Ma and Liu[14] , { I(G) = min
} |X| : X ⊆ V (G), i(G − X) ≥ 2 , i(G − X)
if G is not a complete graph; otherwise, I(G) = +∞. A subset X of V (G) is said to be an independent set (a covering set) of G if each edge of G is incident with at most (at least) one vertex of X. It is easy to deduce that a subset X of V (G) is an independent set of G if and only if V (G) \ X is a covering set of G. Let a ≤ b be two positive integers. A spanning subgraph F of a graph G with a ≤ dF (x) ≤ b for each x ∈ V (G) is called an [a, b]-factor. Especially, an [r, r]-factor is simply called an rfactor. An [a, b]-factor including a Hamiltonian cycle is called a Hamiltonian [a, b]-factor. A graph G is a k-Hamiltonian graph if G − U contains a Hamiltonian cycle for any U ⊆ V (G) with |U | = k. We say that a graph G includes a k-Hamiltonian [a, b]-factor if G − U admits Manuscript received August 26, 2014. Accepted on January 14, 2020. This paper is supported by the National Natural Science Foundation of China (Grant No. 11371009) and the National Social Science Foundation of China (Grant No. 14AGL001), and sponsored by Six Big Talent Peak of Jiangsu Province (Grant No. JY–
Data Loading...
