Displaying similar documents to “A note on a new condition implying pancyclism”

Extension of several sufficient conditions for Hamiltonian graphs

Ahmed Ainouche (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a 2-connected graph of order n. Suppose that for all 3-independent sets X in G, there exists a vertex u in X such that |N(X∖u)|+d(u) ≥ n-1. Using the concept of dual closure, we prove that 1. G is hamiltonian if and only if its 0-dual closure is either complete or the cycle C₇ 2. G is nonhamiltonian if and only if its 0-dual closure is either the graph ( K r K K ) K , 1 ≤ r ≤ s ≤ t or the graph ( ( n + 1 ) / 2 ) K K ( n - 1 ) / 2 . It follows that it takes a polynomial time to check the hamiltonicity or the nonhamiltonicity...

Forbidden triples implying Hamiltonicity: for all graphs

Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson (2004)

Discussiones Mathematicae Graph Theory

Similarity:

In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with G i = K 1 , 3 for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a K 1 , s , s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being K 1 , 3 , such that all...

Hamiltonian colorings of graphs with long cycles

Ladislav Nebeský (2003)

Mathematica Bohemica

Similarity:

By a hamiltonian coloring of a connected graph G of order n 1 we mean a mapping c of V ( G ) into the set of all positive integers such that | c ( x ) - c ( y ) | n - 1 - D G ( x , y ) (where D G ( x , y ) denotes the length of a longest x - y path in G ) for all distinct x , y G . In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order n 5 with circumference n - 2 .

Potential forbidden triples implying hamiltonicity: for sufficiently large graphs

Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson (2005)

Discussiones Mathematicae Graph Theory

Similarity:

In [1], Brousek characterizes all triples of connected graphs, G₁,G₂,G₃, with G i = K 1 , 3 for some i = 1,2, or 3, such that all G₁G₂ G₃-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁,G₂,G₃, none of which is a K 1 , s , s ≥ 3 such that G₁G₂G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G₁,G₂,G₃ with none being K 1 , 3 , such that all G₁G₂G₃-free...

Variations on a sufficient condition for Hamiltonian graphs

Ahmed Ainouche, Serge Lapiquonne (2007)

Discussiones Mathematicae Graph Theory

Similarity:

Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition N G ( x ) N G [ u ] N G [ v ] , where N G [ x ] = N G ( x ) x . In particular, this condition is satisfied if x does not center a claw (an induced K 1 , 3 ). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = x,y,z we define σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|. Flandrin et al. proved that a 2-connected graph G is hamiltonian...

Problems remaining NP-complete for sparse or dense graphs

Ingo Schiermeyer (1995)

Discussiones Mathematicae Graph Theory

Similarity:

For each fixed pair α,c > 0 let INDEPENDENT SET ( m c n α ) and INDEPENDENT SET ( m ( ) - c n α ) be the problem INDEPENDENT SET restricted to graphs on n vertices with m c n α or m ( ) - c n α edges, respectively. Analogously, HAMILTONIAN CIRCUIT ( m n + c n α ) and HAMILTONIAN PATH ( m n + c n α ) are the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with m n + c n α edges. For each ϵ > 0 let HAMILTONIAN CIRCUIT (m ≥ (1 - ϵ)(ⁿ₂)) and HAMILTONIAN PATH (m ≥ (1 - ϵ)(ⁿ₂)) be the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH...

The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs

Ladislav Nebeský (2006)

Czechoslovak Mathematical Journal

Similarity:

If G is a connected graph of order n 1 , then by a hamiltonian coloring of G we mean a mapping c of V ( G ) into the set of all positive integers such that | c ( x ) - c ( y ) | n - 1 - D G ( x , y ) (where D G ( x , y ) denotes the length of a longest x - y path in G ) for all distinct x , y V ( G ) . Let G be a connected graph. By the hamiltonian chromatic number of G we mean min ( max ( c ( z ) ; z V ( G ) ) ) , where the minimum is taken over all hamiltonian colorings c of G . The main result of this paper can be formulated as follows: Let G be a connected graph of order n 3 . Assume that there exists...

Extremal problems for forbidden pairs that imply hamiltonicity

Ralph Faudree, András Gyárfás (1999)

Discussiones Mathematicae Graph Theory

Similarity:

Let C denote the claw K 1 , 3 , N the net (a graph obtained from a K₃ by attaching a disjoint edge to each vertex of the K₃), W the wounded (a graph obtained from a K₃ by attaching an edge to one vertex and a disjoint path P₃ to a second vertex), and Z i the graph consisting of a K₃ with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a k-connected graph G of order n that is CY-free...

On a family of cubic graphs containing the flower snarks

Jean-Luc Fouquet, Henri Thuillier, Jean-Marie Vanherpe (2010)

Discussiones Mathematicae Graph Theory

Similarity:

We consider cubic graphs formed with k ≥ 2 disjoint claws C i K 1 , 3 (0 ≤ i ≤ k-1) such that for every integer i modulo k the three vertices of degree 1 of C i are joined to the three vertices of degree 1 of C i - 1 and joined to the three vertices of degree 1 of C i + 1 . Denote by t i the vertex of degree 3 of C i and by T the set t , t , . . . , t k - 1 . In such a way we construct three distinct graphs, namely FS(1,k), FS(2,k) and FS(3,k). The graph FS(j,k) (j ∈ 1,2,3) is the graph where the set of vertices i = 0 i = k - 1 V ( C i ) T induce j cycles (note...

Pancyclism and small cycles in graphs

Ralph Faudree, Odile Favaron, Evelyne Flandrin, Hao Li (1996)

Discussiones Mathematicae Graph Theory

Similarity:

We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (dC(u,v)+1, [(n+19)/13]), d C ( u , v ) being the distance of u and v on a hamiltonian cycle...

Measures of traceability in graphs

Varaporn Saenpholphat, Futaba Okamoto, Ping Zhang (2006)

Mathematica Bohemica

Similarity:

For a connected graph G of order n 3 and an ordering s v 1 , v 2 , , v n of the vertices of G , d ( s ) = i = 1 n - 1 d ( v i , v i + 1 ) , where d ( v i , v i + 1 ) is the distance between v i and v i + 1 . The traceable number t ( G ) of G is defined by t ( G ) = min d ( s ) , where the minimum is taken over all sequences s of the elements of V ( G ) . It is shown that if G is a nontrivial connected graph of order n such that l is the length of a longest path in G and p is the maximum size of a spanning linear forest in G , then 2 n - 2 - p t ( G ) 2 n - 2 - l and both these bounds are sharp. We establish a formula for the traceable...