Graph Invariants and Large Cycles: A Survey

Abstract

Graph invariants provide a powerful analytical tool for investigation of abstract substructures of graphs. This paper is devoted to large cycle substructures, namely, Hamilton, longest and dominating cycles and some generalized cycles including Hamilton and dominating cycles as special cases. In this paper, we have collected 36 pure algebraic relations between basic (initial) graph invariants ensuring the existence of a certain type of large cycles. These simplest kind of relations having no forerunners in the area actually form a source from which nearly all possible hamiltonian results (including well-known Ore's theorem, Posa's theorem, and many other generalizations) can be developed further by various additional new ideas, generalizations, extensions, restrictions, and structural limitations.

Recommended by Howard Bell

Institute for Informatics and Automation Problems, National Academy of Sciences, P. Sevak 1, Yerevan 0014, Armenia

Received 30 December 2010; Accepted 1 February 2011

1. Introduction

Graph invariants provide a powerful and may be the single analytical tool for investigation of abstract structures of graphs. They, combined in convenient algebraic relations, contain global and general information about a graph and its particular substructures such as cycle structures, factors, matchings, colorings, and coverings. The discovery of these relations is the primary problem of graph theory.

This paper is devoted to large cycle substructures, perhaps the most important cycle structures in graphs: Hamilton, longest and dominating cycles and some generalized cycles including Hamilton and dominating cycles as special cases.

In the literature, eight basic (initial) invariants of a graph G are known having significant impact on large cycle structures, namely, order n , size q , minimum degree δ , connectivity κ , independence number α , toughness τ and the lengths of a longest path and a longest cycle in G\C for a given longest cycle C , denoted by p¯ and c¯ , respectively.

In this paper we have collected 36 pure algebraic relations between basic graph invariants ensuring the existence of a certain type of large cycles. The majority of these results are sharp in all respects.

Focusing only on basic graph invariants, as well as on pure algebraic relations between these parameters, in fact, we present the simplest kind of relations for large cycles having no forerunners in the area. Actually they form a source from which nearly all possible hamiltonian results (including well-known Ore's theorem, Posa's theorem, and many other generalizations) can be developed further by various additional new ideas, generalizations, extensions, restrictions, and structural limitations such as:

(i) generalized and extended graph invariants : degree sequences (Pósa type, Chvatal type), degree sums (Ore type, Fun type), neighborhood unions, generalized degrees, local connectivity, and so on,

(ii) extended list of path and cycle structures : Hamilton, longest and dominating cycles, generalized cycles including Hamilton and dominating cycles as special cases, 2-factor, multiple Hamilton cycles, edge disjoint Hamilton cycles, powers of Hamilton cycles, k -ordered Hamilton cycles, arbitrary cycles, cycle systems, pancyclic-type cycle systems, cycles containing specified sets of vertices or edges, shortest cycles, analogous path structures, and so on,

(iii): structural (descriptive) limitations : regular, planar, bipartite, chordal and interval graphs, graphs with forbidden subgraphs, Boolean graphs, hypercubes, and so on,

(iv) graph extensions : hypergraphs, digraphs and orgraphs, labeled and weighted graphs, infinite graphs, random graphs, and so on.

These 36 initial relations are quite sufficient for interested reader to make a clear imagination about developmental mechanisms in hamiltonian graph theory including the origins, current processes, and future possible developments along with various research problems.

We refer to [1-3] for more background and general surveys.

The order n , size q , and minimum degree δ clearly are easy computable graph invariants. In [4], it was proved that connectivity κ can be determined in polynomial time, as well. Determining the independence number α and toughness τ are shown in [5, 6] to be NP -hard problems. Moreover, it was proved [6] that for any positive rational number t , recognizing t -tough graphs (in particular 1-tough graphs) is an NP -hard problem.

The order n and size q are neutral with respect to cycle structures. Meanwhile, they become more effective combined together (Theorem 3.1). The minimum degree δ having high frequency of occurrence in different relations is, in a sense, a more essential invariant than the order and size, providing some dispersion of the edges in a graph. The combinations between order n and minimum degree δ become much more fruitful especially under some additional connectivity conditions. The impact of some relations on cycle structures can be strengthened under additional conditions of the type δ≥α±i for appropriate integer i . By many graph theorists, the connectivity κ is at the heart of all path and cycle questions providing comparatively more uniform dispersion of the edges. An alternate connectedness measure is toughness τ --the most powerful and less investigated graph invariant introduced by Chvátal [7] as a means of studying the cycle structure of graphs. Chvátal [7] conjectured that there exists a finite constant _t0 such that every _t0 -tough graph is hamiltonian. This conjecture is still open. We have omitted a number of results involving toughness τ as a parameter since they are far from being best possible.

Large cycle structures are centered around well-known Hamilton (spanning) cycles. Other types of large cycles were introduced for different situations when the graph contains no Hamilton cycles or it is difficult to find it. Generally, a cycle C in a graph G is a large cycle if it dominates some certain subgraph structures in G in a sense that every such structure has a vertex in common with C . When C dominates all vertices in G then C is a Hamilton cycle. When C dominates all edges in G then C is called a dominating cycle introduced by Nash-Williams [8]. Further, if C dominates all paths in G of length at least some fixed integer λ then C is a P_Dλ (path dominating)-cycle introduced by Bondy [9]. Finally, if C dominates all cycles in G of length at least λ then C is a C_Dλ (cycle dominating)-cycle, introduced in [10]. The existence problems of generalized P_Dλ and C_Dλ -cycles are studied in [10].

Section 2 is devoted to necessary notation and terminology. In Section 3, we discuss pure relations between various basic invariants of a graph and Hamilton cycles. Next sections are devoted to analogous pure relations concerning dominating cycles (Section 4), C_Dλ -cycles (Section 5), long cycles (Section 6), long cycles with Hamilton cycles (Section 7), long cycles with dominating cycles (Section 8), and long cycles with C_Dλ -cycles (Section 9).

2. Terminology

Throughout this paper we consider only finite undirected graphs without loops or multiple edges. A good reference for any undefined terms is [11]. We reserve n , q , δ , κ , and α to denote the number of vertices (order), number of edges (size), minimum degree, connectivity, and independence number of a graph, respectively. Each vertex and edge in a graph can be interpreted as simple cycles of lengths 1 and 2, respectively. A graph G is hamiltonian if G contains a Hamilton cycle, that is, a cycle containing every vertex of G . The length c of a longest cycle in a graph is called the circumference. For C a longest cycle in G , let p¯ and c¯ denote the lengths of a longest path and a longest cycle in G\C , respectively. A cycle ^{C[variant prime]} in G is a P_Dλ -cycle if |P|≤λ-1 for each path P in G\^{C[variant prime]} and is a C_Dλ -cycle if |^{C[variant prime][variant prime]} |≤λ-1 for each cycle ^{C[variant prime][variant prime]} in G\^{C[variant prime]} . In particular, P_D0 -cycles and C_D1 -cycles are well-known Hamilton cycles and P_D1 -cycles and C_D2 -cycles are often called dominating cycles. Let s(G) denote the number of components of a graph G . A graph G is t -tough if |S|≥ts(G\S) for every subset S of the vertex set V(G) with s(G\S)>1 . The toughness of G , denoted τ(G) , is the maximum value of t for which G is t -tough (taking τ(_Kn )=∞ for all n≥1 ).

Let a,b,t,k be integers with k≤t . We use H(a,b,t,k) to denote the graph obtained from t_Ka +_K¯t by taking any k vertices in subgraph _K¯t and joining each of them to all vertices of _Kb . Let _Lδ be the graph obtained from 3_Kδ +_K1 by taking one vertex in each of three copies of _Kδ and joining them each to other. For odd n≥15 , construct the graph _Gn from _K¯(n-1)/2 +_Kδ +_K(n+1)/2-δ , where n/3≤δ≤(n-5)/2 , by joining every vertex in _Kδ to all other vertices and by adding a matching between all vertices in _K(n+1)/2-δ and (n+1)/2-δ vertices in _K¯(n-1)/2 . It is easily seen that _Gn is 1-tough but not hamiltonian. A variation of the graph _Gn , with _Kδ replaced by _K¯δ and δ=(n-5)/2 , will be denoted by ^Gn* .

3. Hamilton Cycles

We begin with a size lower bound insuring the existence of a Hamilton cycle based on the idea that if a sufficient number of edges are present in the graph on n vertices, then a Hamilton cycle will exist.

Theorem 3.1 (Erdös and Gallai [12]).

Every graph with q≥(ⁿ² -3n+5)/2 is hamiltonian.

Example for Sharpness . To see that the size bound (ⁿ² -3n+5)/2 in Theorem 3.1 is best possible, note that the graph formed by joining one vertex of _Kn-1 to _K1 , contains (ⁿ² -3n+4)/2 edges and is not hamiltonian.

The earliest sufficient condition for a graph to be hamiltonian is based on the order n and minimum degree δ , ensuring the existence of a Hamilton cycle in a graph with sufficient number of edges by keeping the minimum degree at a fairly high level.

Theorem 3.2 (Dirac [13]).

Every graph with δ≥n/2 is hamiltonian.

Example for sharpness: 2_Kδ +_K1 .

The graph 2_Kδ +_K1 shows that the bound n/2 in Theorem 3.2 cannot be replaced by (n-1)/2 .

In [14], it was proved that the minimum degree bound n/2 in Theorem 3.2 can be slightly relaxed for graphs on n≥11 vertices under additional 1-tough condition.

Theorem 3.3 (Jung [14]).

Every graph with n≥11 , τ≥1 and δ≥(n-4)/2 is hamiltonian.

Examples for sharpness: _Kδ,δ+1 ; ^Gn* .

This bound (n-4)/2 itself was lowered further to (n-7)/2 under stronger conditions n≥30 and τ>1 .

Theorem 3.4 (Bauer et al. [15]).

Every graph with n≥30 , τ>1 and δ≥(n-7)/2 is hamiltonian.

In 1981, the Dirac's level n/2 was essentially lowered to (n+κ)/3 when κ<n/2 by incorporating connectivity κ into the minimum degree bound.

Theorem 3.5 (Nikoghosyan [16]).

Every graph with κ≥2 and δ≥(n+κ)/3 is hamiltonian.

Examples for sharpness: 2_Kδ +_K1 ; H(1,δ-κ+1,δ,κ) (2≤κ<n/2) .

A short proof of Theorem 3.5 was given by Häggkvist [17].

The bound (n+κ)/3 in Theorem 3.5 was slightly lowered to (n+κ-2)/3 for 1-tough graphs.

Theorem 3.6 (Bauer and Schmeichel [18]).

Every graph with τ≥1 and δ≥(n+κ-2)/3 is hamiltonian.

Examples for sharpness: _Kδ,δ+1 ; _Lδ .

Another essential improvement of Dirac's lower bound n/2 was established in 1971 due to Nash-Williams under additional condition δ≥α .

Theorem 3.7 (Nash-Williams [8]).

Every graph with κ≥2 and δ≥max {(n+2)/3,α} is hamiltonian.

Examples for sharpness: (λ+1)_Kδ-λ+1 +_Kλ (δ≥2λ) ; (λ+2)_Kδ-λ +_Kλ+1 (δ≥2λ+1) ; H(λ,λ+1,λ+3,λ+2) .

Theorem 3.7 was slightly improved by replacing the condition κ≥2 with τ≥1 .

Theorem 3.8 (Bigalke and Jung [19]).

Every graph with τ≥1 and δ≥max {n/3,α-1} is hamiltonian.

Examples for sharpness: _Kδ,δ+1 (n≥3) ; _Lδ (n≥7) ; _Kδ,δ+1 (n≥3) .

The bound (n+2)/3 in Theorem 3.7 was essentially lowered under additional condition of the type δ≥α+λ including Theorem 3.7 as a special case.

Theorem 3.9 (Fraisse [20]).

Let G be a graph, λ a positive integer and δ≥max {(n+2)/(λ+2)+λ-1,α+λ-1} . If κ≥λ+1 then G is hamiltonian.

Examples for sharpness: (λ+1)_Kδ-λ+1 +_Kλ (δ≥2λ) ; (λ+2)_Kδ-λ +_Kλ+1 (δ≥2λ+1) ; H(λ,λ+1,λ+3,λ+2) .

Later, Theorem 3.7 was essentially improved by incorporating the connectivity κ into the minimum degree bound.

Theorem 3.10 (Nikoghosyan [21]).

Every graph with κ≥3 and δ≥max {(n+2κ)/4,α} is hamiltonian.

Examples for sharpness: 3_K2 +_K2 ; 4_K2 +_K3 , H(1,2,κ+1,κ) .

The graph 4_K2 +_K3 shows that for κ=3 the minimum degree bound (n+2κ)/4 in Theorem 3.10 cannot be replaced by (n+2κ-1)/4 .

Finally, the bound (n+2κ)/4 in Theorem 3.10 was reduced to (n+κ+3)/4 without any limitations providing a best possible result for each κ≥3 .

Theorem 3.11 (Yamashita [22]).

Every graph with κ≥3 and δ≥max {(n+κ+3)/4,α} is hamiltonian.

Examples for sharpness: 3_Kδ-1 +_K2 ; H(2,n-3δ+3,δ-1,κ) ; H(1,2,κ+1,κ) .

The first pure relation between graph invariants involving connectivity κ as a parameter was developed in 1972 due to Chvátal and Erdös [23].

Theorem 3.12 (Chvátal and Erdös [23]).

Every graph with κ≥α is hamiltonian.

Example for sharpness: _Kδ,δ+1 .

4. Dominating Cycles

In 1971, Nash-Williams [8] proved that the minimum degree bound (n+2)/3 insures the existence of dominating cycles.

Theorem 4.1 (Nash-Williams [8]).

Let G be a graph with δ≥(n+2)/3 . If κ≥2 then each longest cycle in G is a dominating cycle.

Examples for sharpness: 2_K3 +_K1 ; 3_Kδ-1 +_K2 ; H(1,2,4,3) .

The graph 2_K3 +_K1 shows that the connectivity condition κ≥2 in Theorem 4.1 cannot be replaced by κ≥1 . The second graph shows that the minimum degree condition δ≥(n+2)/3 cannot be replaced by δ≥(n+1)/2 . Finally, the third graph shows that the conclusion "is a dominating cycle" cannot be strengthened by replacing it with "is a Hamilton cycle".

Further, it was proved that the condition δ≥(n+2)/3 in Theorem 4.1 can be slightly relaxed under stronger 1-tough condition instead of κ≥2 .

Theorem 4.2 (Bigalke and Jung [19]).

Let G be a graph with τ≥1 and δ≥n/3 . Then each longest cycle in G is a dominating cycle.

Examples for sharpness: 2(κ+1)_K2 +κ_K1 ; _L3 ; ^Gn* .

Lu et al. [24] lowered the bound (n+2)/3 in Theorem 4.1 to (n+2κ)/4 by incorporating the connectivity κ into the minimum degree bound.

Theorem 4.3 (Lu et al. [24]).

Let G be graph with κ≥3 and δ≥(n+2κ)/4 . Then each longest cycle in G is a dominating cycle.

Examples for sharpness: 3_K2 +_K2 ; 4_K2 +_K3 ; H(1,2,κ+1,κ) .

The graph 4_K2 +_K3 shows that for κ=3 the minimum degree bound (n+2κ)/4 in Theorem 4.3 cannot be replaced by (n+2κ-1)/4 .

In 2008, the bound (n+2κ)/4 itself was essentially reduced to (n+κ+3)/4 by Yamashita [22] without any additional limitations providing a best possible result for each κ≥3 .

Theorem 4.4 (Yamashita [22]).

Let G be graph with κ≥3 and δ≥(n+κ+3)/4 . Then each longest cycle in G is a dominating cycle.

Examples for sharpness: 3_Kδ-1 +_K2 ; H(2,n-3δ+3,δ-1,κ) ; H(1,2,κ+1,κ) .

5. C_Dλ -Cycles

In 1990, Jung [25] proved the exact analog of Theorems 3.2 and 4.1 concerning C_D3 -cycles.

Theorem 5.1 (Jung [25]).

Let G be a graph with δ≥(n+6)/4 . If κ≥3 then each longest cycle in G is a C_D3 -cycle.

Examples for sharpness: λ_Kλ+1 +_Kλ-1 (λ≥2) ; (λ+1)_Kδ-λ+1 +_Kλ (λ≥1) ; H(λ-1,λ,λ+2,λ+1) (λ≥2) .

In 2009, the author was able to find a common generalization of Theorems 3.2, 4.1, and 5.1 by covering C_Dλ -cycles for all λ≥1 .

Theorem 5.2 (Nikoghosyan [10]).

Let G be a graph, λ a positive integer, and δ≥(n+2)/(λ+1)+λ-2 . If κ≥λ then each longest cycle in G is a C_{Dmin {λ,δ-λ+1}} -cycle.

Examples for sharpness: λ_Kλ+1 +_Kλ-1 (λ≥2) ; (λ+1)_Kδ-λ+1 +_Kλ (λ≥1) ; H(λ-1,λ,λ+2,λ+1) (λ≥2) .

An analogous generalization has been conjectured [10] in terms of P_Dλ -cycles.

Conjecture 5.3 (Nikoghosyan [10]).

Let G be a graph, λ a positive integer, and δ≥(n+2)/(λ+1)+λ-2 . If κ≥λ then each longest cycle in G is a P_{Dmin {λ-1,δ-λ}} -cycle.

In view of Theorems 3.5 and 4.4, the next generalization seems reasonable.

Conjecture 5.4 (Yamashita [22]).

Let G be graph and λ an integer. If κ≥λ≥2 and δ≥(n+κ+λ(λ-2))/(λ+1) then each longest cycle in G is a P_Dλ-2 and C_Dλ-1 -cycle.

6. Long Cycles

The earliest and simplest hamiltonian result [13] links the circumference c and minimum degree δ .

Theorem 6.1 (Dirac [13]).

In every graph, c≥δ+1 .

Example for sharpness: Join two copies of _Kδ+1 by an edge.

For C a longest cycle in a graph G , a lower bound for |C| was developed based on the minimum degree δ and p¯ --the length of a longest path in G\C .

Theorem 6.2 (Nikoghosyan [26]).

Let G be a graph and C a longest cycle in G . Then |C|≥(p¯+2)(δ-p¯) .

Example for sharpness: (κ+1)_Kδ-κ+1 +_Kκ .

The next bound is based on δ and c¯ --the length of a longest cycle in G\C .

Theorem 6.3 (Nikoghosyan [27]).

Let G be a graph and C a longest cycle in G . Then |C|≥(c¯+1)(δ-c¯+1) .

Example for sharpness: (κ+1)_Kδ-κ+1 +_Kκ .

In 2000, the author was able to find an improvement of Theorem 6.3 involving connectivity κ as a parameter combined with c¯ and δ such that the bound grows as κ and c¯ grow.

Theorem 6.4 (Nikoghosyan [28]).

Let G be a graph with κ≥2 and C a longest cycle in G . If c¯≥κ then |C|≥((c¯+1)κ/(c¯+κ+1))(δ+2) . Otherwise, |C|≥((c¯+1)c¯/2(c¯+1))(δ+2) .

Example for sharpness: (κ+1)_Kδ-κ+1 +_Kκ .

In view of Theorem 6.4, the following seems reasonable for P_Dλ -cycles.

Conjecture 6.5 (Nikoghosyan [10]).

Let G be a graph with κ≥2 and C a longest cycle in G . If p¯≥κ-1 then |C|≥((p¯+2)κ/(p¯+κ+2))(δ+2) . Otherwise, |C|≥((p¯+2)p¯/(2p¯+2))(δ+2) .

7. Hamilton Cycles and Long Cycles

The following direct generalization includes Theorem 3.2 as a special case.

Theorem 7.1 (Alon [29]).

Let G be a graph and λ a positive integer. If δ≥n/(λ+1) then c≥n/λ .

Examples for sharpness: (λ+1)_Kλ +_K1 ; λ_Kλ+1 .

Dirac's well-known paper [13] includes the third earliest hamiltonian relationship between minimum degree δ , circumference c , and Hamilton cycles.

Theorem 7.2 (Dirac [13]).

Let G be a graph with κ≥2 . Then c≥min {n,2δ} .

Examples for sharpness: (λ+1)_Kλ+1 +_Kλ (λ≥1) ; (λ+3)_Kλ-1 +_Kλ+2 (λ≥2) ; (λ+2)_Kλ +_Kλ+1 (λ≥1) .

For 1-tough graphs the bound 2δ in Theorem 7.2 was slightly enlarged.

Theorem 7.3 (Bauer and Schmeichel [30]).

Let G be a graph with τ≥1 . Then c≥min {n,2δ+2} .

Examples for sharpness: _Kδ,δ+1 ; _L2 .

The first essential improvement of Theorem 7.2 was achieved by incorporating connectivity κ into the relation without any essential limitation.

Theorem 7.4 (Nikoghosyan [16]).

Let G be a graph with κ≥3 . Then c≥min {n,3δ-κ} .

Examples for sharpness: 3_Kδ-1 +_K2 ; H(1,δ-κ+1,δ,κ) .

A simple proof of Theorem 7.4 was given in [31].

In [32], it was proved that the bound min {n,2δ} in Theorem 7.2 can be essentially enlarged under additional condition δ≥α combined with κ≥3 .

Theorem 7.5 (Voss and Zuluaga [32]).

Let G be a graph with κ≥3 . If δ≥α then c≥min {n,3δ-3} .

Examples for sharpness: (λ+2)_Kλ+2 +_Kλ+1 ; (λ+4)_Kλ +_Kλ+3 ; (λ+3)_Kλ+1 +_Kλ+2 .

This theorem itself has been directly generalized by the following way.

Theorem 7.6 (Nikoghosyan [10]).

Let G be a graph and λ a positive integer. If κ≥λ+2 and δ≥α+λ-1 then c≥min {n,(λ+2)(δ-λ)} .

Examples for sharpness: (λ+2)_Kλ+2 +_Kλ+1 ; (λ+4)_Kλ +_Kλ+3 ; (λ+3)_Kλ+1 +_Kλ+2 .

The bound 3δ-κ in Theorem 7.4 was enlarged to 4δ-2κ under additional condition δ≥α combined with κ≥4 .

Theorem 7.7 (Nikoghosyan [33]).

Let G be a graph with κ≥4 and δ≥α . Then c≥min {n,4δ-2κ} .

Examples for sharpness: 4_K2 +_K3 ; H(1,n-2δ,δ,κ) ; 5_K2 +_K4 .

The bound 4δ-2κ in Theorem 7.7 is sharp for κ=4 .

Furthermore, the bound 4δ-2κ in Theorem 7.7 was essentially improved to 4δ-κ-4 without any additional limitations providing a best possible result for each κ≥4 .

Theorem 7.8 (M. Zh. Nikoghosyan and Zh. G. Nikoghosyan [34]).

Let G be a graph with κ≥4 and δ≥α . Then c≥min {n,4δ-κ-4} .

Examples for sharpness: 4_Kδ-2 +_K3 ; H(1,2,κ+1,κ) ; H(2,n-3δ+3,δ-1,κ) .

The next theorem provides a lower bound for the circumference in terms of n,δ,α under the hypothesis of Theorem 4.1.

Theorem 7.9 (Bauer et al. [35]).

Let G be a graph with κ≥2 . If δ≥(n+2)/3 then c≥min {n,n+δ-α} .

Examples for sharpness: 2_Kδ +_K1 ; 3_Kδ-1 +_K2 ; _K2δ-2,δ .

Theorem 7.9 was improved by the same way.

Theorem 7.10 (Bauer et al. [36]).

Let G be a graph with τ≥1 and δ≥n/3 . Then c≥min {n,n+δ-α+1} .

Examples for sharpness: _Kδ,δ+1 ; _Lδ ; ^Gn* .

8. Dominating Cycles and Long Cycles

In 1977, Voss and Zuluaga [32] proved the exact analog of Theorem 7.2 for dominating cycles.

Theorem 8.1 (Voss and Zuluaga [32]).

Let G be a graph with κ≥3 . Then either c≥3δ-3 or each longest cycle in G is a dominating cycle.

Examples for sharpness: (λ+1)_Kλ+1 +_Kλ (λ≥1) ; (λ+3)_Kλ-1 +_Kλ+2 (λ≥2) ; (λ+2)_Kλ +_Kλ+1 (λ≥1) .

The bound 3δ-3 in Theorem 8.1 was enlarged to 4δ-2κ by incorporating connectivity κ into the bound.

Theorem 8.2 (Nikoghosyan [37]).

Let G be a graph with κ≥4 . Then either c≥4δ-2κ or G has a dominating cycle.

Examples for sharpness: 4_K2 +_K3 ; 5_K2 +_K4 ; H(1,n-2δ,δ,κ) .

Theorem 8.2 is sharp only for κ=4 as can be seen from 5_K2 +_K4 .

Further, the bound 4δ-2κ in Theorem 8.2 was essentially improved to 4δ-κ-4 without any limitation providing a sharp bound for each κ≥4 .

Theorem 8.3 (M. Zh. Nikoghosyan and Zh. G. Nikoghosyan [34]).

Let G be a graph with κ≥4 . Then either c≥4δ-κ-4 or each longest cycle in G is a dominating cycle.

Examples for sharpness: 4_Kδ-2 +_K3 ; H(2,δ-κ+1,δ-1,κ) ; H(1,2,κ+1,κ) .

9. C_Dλ -Cycles and Long Cycles

The following common generalization covers C_Dλ -cycles for all λ≥1 including Hamilton and dominating cycles (see Theorems 7.2 and 8.1) as special cases.

Theorem 9.1 (Nikoghosyan [10]).

Let G be a graph and λ a positive integer. If κ≥λ+1 then either c≥(λ+1)(δ-λ+1) or each longest cycle in G is a C_{Dmin {λ,δ-λ}} -cycle.

Examples for sharpness: (λ+1)_Kλ+1 +_Kλ (λ≥1) ; (λ+3)_Kλ-1 +_Kλ+2 (λ≥2) ; (λ+2)_Kλ +_Kλ+1 (λ≥1) .

Another version of Theorem 9.1 was conjectured [10] in terms of P_Dλ -cycles.

Conjecture 9.2 (Nikoghosyan [10]).

Let G be a graph and λ a positive integer. If κ≥λ+1 then either c≥(λ+1)(δ-λ+1) or each longest cycle in G is a P_{Dmin {λ-1,δ-λ-1}} -cycle.

In view of Theorems 7.4 and 8.3, the following conjecture seems reasonable.

Conjecture 9.3.

Let G be a graph and λ≥2 an integer. If κ≥λ+1 then either c≥(λ+1)δ-κ-(λ+1)(λ-2) or each longest cycle in G is a P_Dλ-2 and C_Dλ-1 -cycle.

Acknowledgment

The author would like to thank the anonymous referees for careful reading of the paper and for their valuable suggestions.

References

[1] L. W. Beineke, R. G. Wilson Selected Topics in Graph Theory , pp. xii+451, Academic Press, London, UK, 1978.

[2] R. J. Gould, "Updating the Hamiltonian problem--a survey," Journal of Graph Theory , vol. 15, no. 2, pp. 121-157, 1991.

[3] R. J. Gould, "Advances on the Hamiltonian problem--a survey," Graphs and Combinatorics , vol. 19, no. 1, pp. 7-52, 2003.

[4] S. Even, R. E. Tarjan, "Network flow and testing graph connectivity," SIAM Journal on Computing , vol. 4, no. 4, pp. 507-518, 1975.

[5] M. R. Garey, D. S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman, New York, NY, USA, 1983.

[6] D. Bauer, S. L. Hakimi, E. Schmeichel, "Recognizing tough graphs is NP-hard," Discrete Applied Mathematics , vol. 28, no. 3, pp. 191-195, 1990.

[7] V. Chvátal, "Tough graphs and Hamiltonian circuits," Discrete Mathematics , vol. 5, pp. 215-228, 1973.

[8] C. St. J. A. Nash-Williams, L. Mirsky, "Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency," Studies in Pure Mathematics (Presented to Richard Rado) , pp. 157-183, Academic Press, London, UK, 1971.

[9] J. A. Bondy, G. Chartrand, Y. Alavi, D. L. Goldsmith, L. Lesniak-Foster, D. R. Lick, "Integrity in graph theory," The Theory and Applications of Graphs (Kalamazoo, Mich., 1980) , pp. 117-125, Wiley, New York, NY, USA, 1981.

[10] Zh. G. Nikoghosyan, "Dirac-type generalizations concerning large cycles in graphs," Discrete Mathematics , vol. 309, no. 8, pp. 1925-1930, 2009.

[11] J. A. Bondy, U. S. R. Murty Graph Theory with Applications , pp. x + 264, American Elsevier Publishing, New York, NY, USA, 1976.

[12] P. Erdös, T. Gallai, "On maximal paths and circuits of graphs," Acta Mathematica Academiae Scientiarum Hungaricae , vol. 10, pp. 337-356, 1959.

[13] G. A. Dirac, "Some theorems on abstract graphs," Proceedings of the London Mathematical Society , vol. 2, pp. 69-81, 1952.

[14] H. A. Jung, "On maximal circuits in finite graphs," Annals of Discrete Mathematics , vol. 3, pp. 129-144, 1978.

[15] D. Bauer, L. L. Lasser, G. Chen, "A degree condition for Hamiltonian cycles in t -tough graphs with t>1 ," Advances in Graph Theory , pp. 19-32, Vishwa, Gulbarga, India, 1991.

[16] Zh. G. Nikogosyan, "On the maximal cycle of a graph," Akademiya Nauk Armyansko-SSR. Doklady , vol. 72, no. 2, pp. 82-87, 1981.

[17] R. Häggkvist, G. G. Nicoghossian, "A remark on Hamiltonian cycles," Journal of Combinatorial Theory. Series B , vol. 30, no. 1, pp. 118-120, 1981.

[18] D. Bauer, E. Schmeichel, "On a theorem of Häggkvist and Nicoghossian," Graph Theory, Combinatorics, Algorithms, and Applications (San Francisco, CA, 1989) , pp. 20-25, SIAM, Philadelphia, Pa, USA, 1991.

[19] A. Bigalke, H. A. Jung, "Über Hamiltonsche Kreise und unabhängige Ecken in Graphen," Monatshefte für Mathematik , vol. 88, no. 3, pp. 195-210, 1979.

[20] P. Fraisse, " _Dλ -cycles and their applications for Hamiltonian graphs," preprint, 1986

[21] Zh. G. Nikoghosyan, "A sufficient condition for a graph to be Hamiltonian," Matematicheskie Voprosy Kibernetiki i Vichislitelnoy Tekhniki , vol. 14, pp. 34-54, 1985.

[22] T. Yamashita, "A degree sum condition with connectivity for relative length of longest paths and cycles," Discrete Mathematics , vol. 309, no. 23-24, pp. 6503-6507, 2009.

[23] V. Chvátal, P. Erdös, "A note on Hamiltonian circuits," Discrete Mathematics , vol. 2, pp. 111-113, 1972.

[24] M. Lu, H. Liu, F. Tian, "Two sufficient conditions for dominating cycles," Journal of Graph Theory , vol. 49, no. 2, pp. 135-150, 2005.

[25] H. A. Jung, R. Bodendieck, R. Henn, "Long cycles in graphs with moderate connectivity," Topics in Combinatorics and Graph Theory (Oberwolfach, 1990) , pp. 765-778, Physica, Heidelberg, Germany, 1990.

[26] Zh. G. Nikoghosyan, "Path-extensions and long cycles in graphs, Transactions of the Institute for Informatics and Automation Problems of the NAS (Republic of Armenia) and Yerevan State University," Mathematical Problems of Computer Science , vol. 19, pp. 25-31, 1998.

[27] Zh. G. Nikoghosyan, "Cycle-extensions and long cycles in graphs, Transactions of the Institute for Informatics and Automation Problems of the NAS (Republic of Armenia) and Yerevan State University," Mathematical Problems of Computer Science , vol. 21, pp. 121-128, 2000.

[28] Zh. G. Nikoghosyan, "Cycle-extensions and long cycles in k-connected graphs, Transactions of the Institute for Informatics and Automation Problems of the NAS (Republic of Armenia) and Yerevan State University," Mathematical Problems of Computer Science , vol. 21, pp. 129-155, 2000.

[29] N. Alon, "The longest cycle of a graph with a large minimal degree," Journal of Graph Theory , vol. 10, no. 1, pp. 123-127, 1986.

[30] D. Bauer, E. Schmeichel, "Long cycles in tough graphs," preprint, 1987

[31] C. M. Mosesyan, M. Zh. Nikoghosyan, Zh. G. Nikoghosyan, "Simple proofs of two Dirac-type theorems involving connectivity," preprint, http://arxiv.org/abs/0906.3630

[32] H.-J. Voss, C. Zuluaga, "Maximale gerade und ungerade Kreise in Graphen. I," Wissenschaftliche Zeitschrift der Technischen Hochschule Ilmenau , vol. 23, no. 4, pp. 57-70, 1977.

[33] Zh. G. Nikoghosyan, "On maximal cycles in graphs," Akademiya Nauk Armyansko-SSR. Doklady , vol. 81(4), pp. 166-170, 1985.

[34] M. Zh. Nikoghosyan, Zh. G. Nikoghosyan, "Large cycles in 4-connected graphs," Discrete Mathematics , vol. 311, pp. 302-306, 2011.

[35] D. Bauer, H. J. Veldman, A. Morgana, E. F. Schmeichel, "Long cycles in graphs with large degree sums," Discrete Mathematics , vol. 79, no. 1, pp. 59-70, 1990.

[36] D. Bauer, H. J. Veldman, E. F. Schmeichel, "A generalization of a theorem of Bigalke and Jung," Ars Combinatoria , vol. 26, pp. 53-58, 1988.

[37] Zh. G. Nikoghosyan, "On the circumference, connectivity and dominating cycles," preprint, http://arxiv.org/abs/0906.1857