# Graph Invariants and Large Cycles: A Survey

Authors: Zh. G. Nikoghosyan
Journal: International Journal of Mathematics and Mathematical Sciences
 (2011)

---

## 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.


---

## Body

## 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 graphG 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 ordern, 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 ordern 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 cycleC 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 PDλ (path dominating)-cycle introduced by Bondy [9]. Finally, if C dominates all cycles in G of length at least λ then C is a CDλ (cycle dominating)-cycle, introduced in [10]. The existence problems of generalized PDλ and CDλ-cycles are studied in [10].Section2 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), CDλ-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 CDλ-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′ in G is a PDλ-cycle if |P|≤λ-1 for each path P in G∖C′ and is a CDλ-cycle if |C′′|≤λ-1 for each cycle C′′ in G∖C′. In particular, PD0-cycles and CD1-cycles are well-known Hamilton cycles and PD1-cycles and CD2-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).Leta,b,t,k be integers with k≤t. We use H(a,b,t,k) to denote the graph obtained from tKa+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 3Kδ+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 onn vertices, then a Hamilton cycle will exist.Theorem 3.1 (Erdös and Gallai [12]).
Every graph withq≥(n2-3n+5)/2 is hamiltonian.Example for Sharpness. To see that the size bound (n2-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 (n2-3n+4)/2 edges and is not hamiltonian.The earliest sufficient condition for a graph to be hamiltonian is based on the ordern 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:2Kδ+K1.The graph2Kδ+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 withn≥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 withn≥30, τ>1 and δ≥(n-7)/2 is hamiltonian.In 1981, the Dirac’s leveln/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:2Kδ+K1; H(1,δ-κ+1,δ,κ)(2≤κ<n/2).A short proof of Theorem3.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 boundn/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).Theorem3.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]).
LetG 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, Theorem3.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:3K2+K2; 4K2+K3, H(1,2,κ+1,κ).The graph4K2+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:3Kδ-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]).
LetG be a graph with δ≥(n+2)/3. If κ≥2 then each longest cycle in G is a dominating cycle.Examples for sharpness:2K3+K1; 3Kδ-1+K2; H(1,2,4,3).The graph2K3+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]).
LetG 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]).
LetG be graph with κ≥3 and δ≥(n+2κ)/4. Then each longest cycle in G is a dominating cycle.Examples for sharpness:3K2+K2; 4K2+K3; H(1,2,κ+1,κ).The graph4K2+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]).
LetG be graph with κ≥3 and δ≥(n+κ+3)/4. Then each longest cycle in G is a dominating cycle.Examples for sharpness:3Kδ-1+K2; H(2,n-3δ+3,δ-1,κ); H(1,2,κ+1,κ).


## 5.CDλ-Cycles

In 1990, Jung [25] proved the exact analog of Theorems 3.2 and 4.1 concerning CD3-cycles.Theorem 5.1 (Jung [25]).
LetG be a graph with δ≥(n+6)/4. If κ≥3 then each longest cycle in G is a CD3-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 Theorems3.2, 4.1, and 5.1 by covering CDλ-cycles for all λ≥1.Theorem 5.2 (Nikoghosyan [10]).
LetG be a graph, λ a positive integer, and δ≥(n+2)/(λ+1)+λ-2. If κ≥λ then each longest cycle in G is a CDmin{λ,δ-λ+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 PDλ-cycles.Conjecture 5.3 (Nikoghosyan [10]).
LetG be a graph, λ a positive integer, and δ≥(n+2)/(λ+1)+λ-2. If κ≥λ then each longest cycle in G is a PDmin{λ-1,δ-λ}-cycle.In view of Theorems3.5 and 4.4, the next generalization seems reasonable.Conjecture 5.4 (Yamashita [22]).
LetG be graph and λ an integer. If κ≥λ≥2 and δ≥(n+κ+λ(λ-2))/(λ+1) then each longest cycle in G is a PDλ-2 and CDλ-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 ofKδ+1 by an edge.ForC 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]).
LetG 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]).
LetG 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 Theorem6.3 involving connectivity κ as a parameter combined with c¯ and δ such that the bound grows as κ and c¯ grow.Theorem 6.4 (Nikoghosyan [28]).
LetG 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 Theorem6.4, the following seems reasonable for PDλ-cycles.Conjecture 6.5 (Nikoghosyan [10]).
LetG 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 Theorem3.2 as a special case.Theorem 7.1 (Alon [29]).
LetG 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]).
LetG 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 bound2δ in Theorem 7.2 was slightly enlarged.Theorem 7.3 (Bauer and Schmeichel [30]).
LetG be a graph with τ≥1. Then c≥min{n,2δ+2}.Examples for sharpness:Kδ,δ+1; L2.The first essential improvement of Theorem7.2 was achieved by incorporating connectivity κ into the relation without any essential limitation.Theorem 7.4 (Nikoghosyan [16]).
LetG be a graph with κ≥3. Then c≥min{n,3δ-κ}.Examples for sharpness:3Kδ-1+K2; H(1,δ-κ+1,δ,κ).A simple proof of Theorem7.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]).
LetG 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]).
LetG 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 bound3δ-κ in Theorem 7.4 was enlarged to 4δ-2κ under additional condition δ≥α combined with κ≥4.Theorem 7.7 (Nikoghosyan [33]).
LetG be a graph with κ≥4 and δ≥α. Then c≥min{n,4δ-2κ}.Examples for sharpness:4K2+K3; H(1,n-2δ,δ,κ); 5K2+K4.The bound4δ-2κ in Theorem 7.7 is sharp for κ=4.Furthermore, the bound4δ-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]).
LetG be a graph with κ≥4 and δ≥α. Then c≥min{n,4δ-κ-4}.Examples for sharpness:4Kδ-2+K3; H(1,2,κ+1,κ); H(2,n-3δ+3,δ-1,κ).The next theorem provides a lower bound for the circumference in terms ofn,δ,α under the hypothesis of Theorem 4.1.Theorem 7.9 (Bauer et al. [35]).
LetG be a graph with κ≥2. If δ≥(n+2)/3 then c≥min{n,n+δ-α}.Examples for sharpness:2Kδ+K1; 3Kδ-1+K2; K2δ-2,δ.Theorem7.9 was improved by the same way.Theorem 7.10 (Bauer et al. [36]).
LetG 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]).
LetG 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 bound3δ-3 in Theorem 8.1 was enlarged to 4δ-2κ by incorporating connectivity κ into the bound.Theorem 8.2 (Nikoghosyan [37]).
LetG be a graph with κ≥4. Then either c≥4δ-2κ or G has a dominating cycle.Examples for sharpness:4K2+K3; 5K2+K4; H(1,n-2δ,δ,κ).Theorem8.2 is sharp only for κ=4 as can be seen from 5K2+K4.Further, the bound4δ-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]).
LetG be a graph with κ≥4. Then either c≥4δ-κ-4 or each longest cycle in G is a dominating cycle.Examples for sharpness:4Kδ-2+K3; H(2,δ-κ+1,δ-1,κ); H(1,2,κ+1,κ).


## 9.CDλ-Cycles and Long Cycles

The following common generalization coversCDλ-cycles for all λ≥1 including Hamilton and dominating cycles (see Theorems 7.2 and 8.1) as special cases.Theorem 9.1 (Nikoghosyan [10]).
LetG be a graph and λ a positive integer. If κ≥λ+1 then either c≥(λ+1)(δ-λ+1) or each longest cycle in G is a CDmin{λ,δ-λ}-cycle.Examples for sharpness:(λ+1)Kλ+1+Kλ(λ≥1); (λ+3)Kλ-1+Kλ+2(λ≥2); (λ+2)Kλ+Kλ+1(λ≥1).Another version of Theorem9.1 was conjectured [10] in terms of PDλ-cycles.Conjecture 9.2 (Nikoghosyan [10]).
LetG be a graph and λ a positive integer. If κ≥λ+1 then either c≥(λ+1)(δ-λ+1) or each longest cycle in G is a PDmin{λ-1,δ-λ-1}-cycle.In view of Theorems7.4 and 8.3, the following conjecture seems reasonable.Conjecture 9.3.
LetG be a graph and λ≥2 an integer. If κ≥λ+1 then either c≥(λ+1)δ-κ-(λ+1)(λ-2) or each longest cycle in G is a PDλ-2 and CDλ-1-cycle.



---

*Source: 206404-2011-05-14.xml*