A Generalization of Implicit Ore-condition for Hamiltonicity of k -connected Graphs
- PDF / 165,904 Bytes
- 7 Pages / 612 x 792 pts (letter) Page_size
- 42 Downloads / 144 Views
Acta Mathemacae Applicatae Sinica, English Series The Editorial Office of AMAS & Springer-Verlag GmbH Germany 2020
A Generalization of Implicit Ore-condition for Hamiltonicity of k-connected Graphs Jun-qing CAI† , Lin WANG School of Management, Qufu Normal University, Rizhao 276826, China (E-mail: [email protected])
Abstract In 2005, Flandrin et al. proved that if G is a k-connected graph of order n and V (G) = X1 ∪ X2 ∪ · · · ∪ Xk such that d(x) + d(y) ≥ n for each pair of nonadjacent vertices x, y ∈ Xi and each i with i = 1, 2, · · · , k, then G is hamiltonian. In order to get more sufficient conditions for hamiltonicity of graphs, Zhu, Li and Deng proposed the definitions of two kinds of implicit degree of a vertex v, denoted by id1 (v) and id2 (v), respectively. In this paper, we are going to prove that if G is a k-connected graph of order n and V (G) = X1 ∪ X2 ∪ · · · ∪ Xk such that id2 (x) + id2 (y) ≥ n for each pair of nonadjacent vertices x, y ∈ Xi and each i with i = 1, 2, · · · , k, then G is hamiltonian. Keywords
implicit degree; Hamiltonian cycle; cyclability
2000 MR Subject Classification
1
05C38; 05C45
Introduction
In this paper, we consider only undirected and finite graphs without loops or multiple edges. Notation and terminology not defined here can be found in [2]. Let G = (V (G), E(G)) be a graph with vertex set V (G) and edge set E(G). For a subset A of V (G), |A| denotes the number of vertices in A. In particular, |V (G)| denotes the order of G. Let H be a subgraph of G and u, v two vertices of V (G), we denote the neighborhood of u in H by NH (u), the degree of u in H by dH (u) = |NH (u)|, the distance between u and v in H by dH (u, v). If H = G, we can use N (u), d(u) and d(u, v) in place of NG (u), dG (u) and dG (u, v), respectively. A graph G is hamiltonian if it contains a hamiltonian cycle, i.e. a cycle that contains all vertices of G. Various sufficient conditions for a graph to be hamiltonian have been given in term of degree conditions. Two of the most well-known are the following conditions due to Ore and Fan, respectively. Theorem 1.1. [17] Let G be a graph of order n ≥ 3. If d(x) + d(y) ≥ n for each pair of nonadjacent vertices x, y ∈ V (G), then G is hamiltonian. Theorem 1.2. [10] Let G be a 2-connected graph of order n ≥ 3. If max{d(u), d(v)} ≥ n/2 for each pair of vertices u and v with d(u, v) = 2, then G is hamiltonian. A subset X ⊆ V (G) is cyclable in G if there is a cycle in G containing all vertices of X. We also say that G is X-cyclable. Clearly, a graph G being hamiltonian is equivalent to G is V (G)-cyclable. Shi and Ota generalized Ore’s theorem to cyclability of graphs, respectively. Manuscript received August 2, 2018. Accepted on January 17, 2020. This paper is supported by the National Natural Science Foundation of China (No.11501322), Scientific Research Foundation for Doctors in Qufu Normal University (No. 2012015) and Natural Science Foundation of Qufu Normal University (No.xkj201415). † Corresponding author.
A Generalization of Implicit Ore-condition for Ha
Data Loading...
