Displaying similar documents to “Cycles with a given number of vertices from each partite set in regular multipartite tournaments”

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 ( γ ) ∩ A ( C ₖ ) | , the number of arcs that γ and Cₖ have in common. Let f ( k , T , γ ) = m a x I γ ( C ₖ ) | C ₖ ⊂ T and f(n,k) = minf(k,T,γ)|T is a hamiltonian tournament with n vertices, and γ a hamiltonian cycle of T. In previous...

Competition hypergraphs of digraphs with certain properties II. Hamiltonicity

Martin Sonntag, Hanns-Martin Teichert (2008)

Discussiones Mathematicae Graph Theory

Similarity:

If D = (V,A) is a digraph, its competition hypergraph (D) has vertex set V and e ⊆ V is an edge of (D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that e = N D ⁻ ( v ) = w ∈ V | ( w , v ) ∈ A . We give characterizations of (D) in case of hamiltonian digraphs D and, more general, of digraphs D having a τ-cycle factor. The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [4] and Guichard [6].

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 ) ) ∩ A ( γ ) | ≥ 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 <...

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

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 ) ) ∩ A ( γ ) | ≥ h ( k ) - 4 and the result is best possible. In a previous paper a similar result for 4 ≤ k ≤ (n+4)/2 was...

The structure of digraphs associated with the congruence x k ≡ y ( mod n )

Lawrence Somer, Michal Křížek (2011)

Czechoslovak Mathematical Journal

Similarity:

We assign to each pair of positive integers n and k ≥ 2 a digraph G ( n , k ) whose set of vertices is H = { 0 , 1 , ⋯ , n - 1 } and for which there is a directed edge from a ∈ H to b ∈ H if a k ≡ b ( mod n ) . We investigate the structure of G ( n , k ) . In particular, upper bounds are given for the longest cycle in G ( n , k ) . We find subdigraphs of G ( n , k ) , called fundamental constituents of G ( n , k ) , for which all trees attached to cycle vertices are isomorphic.

On the heights of power digraphs modulo n

Uzma Ahmad, Husnine Syed (2012)

Czechoslovak Mathematical Journal

Similarity:

A power digraph, denoted by G ( n , k ) , is a directed graph with ℤ n = { 0 , 1 , ⋯ , n - 1 } as the set of vertices and E = { ( a , b ) : a k ≡ b ( mod n ) } as the edge set. In this paper we extend the work done by Lawrence Somer and Michal Křížek: On a connection of number theory with graph theory, Czech. Math. J. 54 (2004), 465–485, and Lawrence Somer and Michal Křížek: Structure of digraphs associated with quadratic congruences with composite moduli, Discrete Math. 306 (2006), 2174–2185. The heights of the vertices and the components of G ( n , k ) for n ≥ 1 and...