Linear forests and ordered cycles

Guantao Chen; Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Linda Lesniak; Florian Pfender

Displaying similar documents to “Linear forests and ordered cycles”

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

A conjecture on cycle-pancyclism in tournaments

Hortensia Galeana-Sánchez, Sergio Rajsbaum (1998)

Discussiones Mathematicae Graph Theory

Similarity:

Let T be a hamiltonian tournament with n vertices and γ a hamiltonian cycle of T. In previous works we introduced and studied the concept of cycle-pancyclism to capture the following question: What is the maximum intersection with γ of a cycle of length k? More precisely, for a cycle Cₖ of length k in T we denote $I_{γ} (C ₖ) = | A (γ) \cap A (C ₖ) |$ , the number of arcs that γ and Cₖ have in common. Let $f (k, T, γ) = m a x I_{γ} (C ₖ) | C ₖ \subset T$ and f(n,k) = minf(k,T,γ)|T is a hamiltonian tournament with n vertices, and γ a hamiltonian cycle of T. In previous...

Cycle-pancyclism in bipartite tournaments I

Hortensia Galeana-Sánchez (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let T be a hamiltonian bipartite tournament with n vertices, γ a hamiltonian directed cycle of T, and k an even number. In this paper, the following question is studied: What is the maximum intersection with γ of a directed cycle of length k? It is proved that for an even k in the range 4 ≤ k ≤ [(n+4)/2], there exists a directed cycle $C_{h (k)}$ of length h(k), h(k) ∈ k,k-2 with $| A (C_{h (k)}) \cap A (γ) | \geq h (k) - 3$ and the result is best possible. In a forthcoming paper the case of directed cycles of length k, k even and k <...

Cycle-pancyclism in bipartite tournaments II

Hortensia Galeana-Sánchez (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let T be a hamiltonian bipartite tournament with n vertices, γ a hamiltonian directed cycle of T, and k an even number. In this paper the following question is studied: What is the maximum intersection with γ of a directed cycle of length k contained in T[V(γ)]? It is proved that for an even k in the range (n+6)/2 ≤ k ≤ n-2, there exists a directed cycle $C_{h (k)}$ of length h(k), h(k) ∈ k,k-2 with $| A (C_{h (k)}) \cap A (γ) | \geq h (k) - 4$ and the result is best possible. In a previous paper a similar result for 4 ≤ k ≤ (n+4)/2 was...

Knotted Hamiltonian cycles in spatial embeddings of complete graphs.

Blain, Paul, Bowlin, Garry, Foisy, Joel, Hendricks, Jacob, LaCombe, Jason (2007)

The New York Journal of Mathematics [electronic only]

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

An upper bound on the basis number of the powers of the complete graphs

Salar Y. Alsardary (2001)

Czechoslovak Mathematical Journal

Similarity:

The basis number of a graph $G$ is defined by Schmeichel to be the least integer $h$ such that $G$ has an $h$ -fold basis for its cycle space. MacLane showed that a graph is planar if and only if its basis number is $\leq 2$ . Schmeichel proved that the basis number of the complete graph $K_{n}$ is at most $3$ . We generalize the result of Schmeichel by showing that the basis number of the $d$ -th power of $K_{n}$ is at most $2 d + 1$ .

Graph invariants and large cycles: a survey.

Nikoghosyan, Zh.G. (2011)

International Journal of Mathematics and Mathematical Sciences

Similarity:

Cycles with a given number of vertices from each partite set in regular multipartite tournaments

Lutz Volkmann, Stefan Winzen (2006)

Czechoslovak Mathematical Journal

Similarity:

If $x$ is a vertex of a digraph $D$ , then we denote by $d^{+} (x)$ and $d^{-} (x)$ the outdegree and the indegree of $x$ , respectively. A digraph $D$ is called regular, if there is a number $p \in ℕ$ such that $d^{+} (x) = d^{-} (x) = p$ for all vertices $x$ of $D$ . A $c$ -partite tournament is an orientation of a complete $c$ -partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular,...

On a Hamiltonian cycle of the fourth power of a connected graph

Elena Wisztová (1991)

Mathematica Bohemica

Similarity:

In this paper the following theorem is proved: Let $G$ be a connected graph of order $p \geq 4$ and let $M$ be a matching in $G$ . Then there exists a hamiltonian cycle $C$ of $G^{4}$ such that $E (C) ⋂ M = 0$ .

A matching and a Hamiltonian cycle of the fourth power of a connected graph

Ladislav Nebeský (1993)

Mathematica Bohemica

Similarity:

The following result is proved: Let $G$ be a connected graph of order $g e q 4$ . Then for every matching $M$ in $G^{4}$ there exists a hamiltonian cycle $C$ of $G^{4}$ such that $E (C) ⋂ M = 0$ .