Extension of several sufficient conditions for Hamiltonian graphs

Ahmed Ainouche

Displaying similar documents to “Extension of several sufficient conditions for Hamiltonian graphs”

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) \subseteq N_{G} [u] \cup N_{G} [v]$ , where $N_{G} [x] = N_{G} (x) \cup 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...

Factors and circuits in $K_{1, 3}$ -free graphs

Zdeněk Ryjáček (1989)

Banach Center Publications

Similarity:

A note on a new condition implying pancyclism

Evelyne Flandrin, Hao Li, Antoni Marczyk, Mariusz Woźniak (2001)

Discussiones Mathematicae Graph Theory

Similarity:

We first show that if a 2-connected graph G of order n is such that for each two vertices u and v such that δ = d(u) and d(v) < n/2 the edge uv belongs to E(G), then G is hamiltonian. Next, by using this result, we prove that a graph G satysfying the above condition is either pancyclic or isomorphic to $K_{n / 2, n / 2}$ .

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

Intersection graph of gamma sets in the total graph

T. Tamizh Chelvam, T. Asir (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we consider the intersection graph $I_{Γ} (ℤ ₙ)$ of gamma sets in the total graph on ℤₙ. We characterize the values of n for which $I_{Γ} (ℤ ₙ)$ is complete, bipartite, cycle, chordal and planar. Further, we prove that $I_{Γ} (ℤ ₙ)$ is an Eulerian, Hamiltonian and as well as a pancyclic graph. Also we obtain the value of the independent number, the clique number, the chromatic number, the connectivity and some domination parameters of $I_{Γ} (ℤ ₙ)$ .

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

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 \leq c n^{α}$ ) and INDEPENDENT SET ( $m \geq (ⁿ ₂) - c n^{α}$ ) be the problem INDEPENDENT SET restricted to graphs on n vertices with $m \leq c n^{α}$ or $m \geq (ⁿ ₂) - c n^{α}$ edges, respectively. Analogously, HAMILTONIAN CIRCUIT ( $m \leq n + c n^{α}$ ) and HAMILTONIAN PATH ( $m \leq n + c n^{α}$ ) are the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with $m \leq 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...

An upper bound of a generalized upper Hamiltonian number of a graph

Martin Dzúrik (2021)

Archivum Mathematicum

Similarity:

In this article we study graphs with ordering of vertices, we define a generalization called a pseudoordering, and for a graph $H$ we define the $H$ -Hamiltonian number of a graph $G$ . We will show that this concept is a generalization of both the Hamiltonian number and the traceable number. We will prove equivalent characteristics of an isomorphism of graphs $G$ and $H$ using $H$ -Hamiltonian number of $G$ . Furthermore, we will show that for a fixed number of vertices, each path has a maximal upper...

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 \geq 1$ we mean a mapping $c$ of $V (G)$ into the set of all positive integers such that $| c (x) - c (y) | \geq 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 \in G$ . In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order $n \geq 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...

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

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 \geq 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) | \geq 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 \in V (G)$ . Let $G$ be a connected graph. By the hamiltonian chromatic number of $G$ we mean $min (max (c (z); z \in 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 \geq 3$ . Assume that there exists...