Displaying similar documents to “Cycle-pancyclism in bipartite tournaments II”

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

Pairs of forbidden class of subgraphs concerning K 1 , 3 and P₆ to have a cycle containing specified vertices

Takeshi Sugiyama, Masao Tsugaki (2009)

Discussiones Mathematicae Graph Theory

Similarity:

In [3], Faudree and Gould showed that if a 2-connected graph contains no K 1 , 3 and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair K 1 , 3 and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.

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

Hamiltonian-colored powers of strong digraphs

Garry Johns, Ryan Jones, Kyle Kolasinski, Ping Zhang (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For a strong oriented graph D of order n and diameter d and an integer k with 1 ≤ k ≤ d, the kth power D k of D is that digraph having vertex set V(D) with the property that (u, v) is an arc of D k if the directed distance d D ( u , v ) from u to v in D is at most k. For every strong digraph D of order n ≥ 2 and every integer k ≥ ⌈n/2⌉, the digraph D k is Hamiltonian and the lower bound ⌈n/2⌉ is sharp. The digraph D k is distance-colored if each arc (u, v) of D k is assigned the color i where i = d D ( u , v ) . The digraph...

A note on arc-disjoint cycles in tournaments

Jan Florek (2014)

Colloquium Mathematicae

Similarity:

We prove that every vertex v of a tournament T belongs to at least m a x m i n δ ( T ) , 2 δ ( T ) - d T ( v ) + 1 , m i n δ ¯ ( T ) , 2 δ ¯ ( T ) - d ¯ T ( v ) + 1 arc-disjoint cycles, where δ⁺(T) (or δ¯(T)) is the minimum out-degree (resp. minimum in-degree) of T, and d T ( v ) (or d ¯ T ( v ) ) is the out-degree (resp. in-degree) of v.

Hamiltonicity of cubic Cayley graphs

Henry Glover, Dragan Marušič (2007)

Journal of the European Mathematical Society

Similarity:

Following a problem posed by Lovász in 1969, it is believed that every finite connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from finite groups having a ( 2 , s , 3 ) -presentation, that is, for groups G = a , b a 2 = 1 , b s = 1 , ( a b ) 3 = 1 , generated by an involution a and an element b of order s 3 such that their product a b has order 3 . More precisely, it is shown that the Cayley graph X = Cay ( G , { a , b , b - 1 } ) has a Hamilton cycle when | G | (and thus s ) is congruent to 2 modulo 4, and has a...

Minimal and minimum size latin bitrades of each genus

James Lefevre, Diane Donovan, Nicholas J. Cavenagh, Aleš Drápal (2007)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Suppose that T and T are partial latin squares of order n , with the property that each row and each column of T contains the same set of entries as the corresponding row or column of T . In addition, suppose that each cell in T contains an entry if and only if the corresponding cell in T contains an entry, and these entries (if they exist) are different. Then the pair T = ( T , T ) forms a . The of T is the total number of filled cells in T (equivalently T ). The latin bitrade is if there is no...

Spectral radius and Hamiltonicity of graphs with large minimum degree

Vladimir Nikiforov (2016)

Czechoslovak Mathematical Journal

Similarity:

Let G be a graph of order n and λ ( G ) the spectral radius of its adjacency matrix. We extend some recent results on sufficient conditions for Hamiltonian paths and cycles in G . One of the main results of the paper is the following theorem: Let k 2 , n k 3 + k + 4 , and let G be a graph of order n , with minimum degree δ ( G ) k . If λ ( G ) n - k - 1 , then G has a Hamiltonian cycle, unless G = K 1 ( K n - k - 1 + K k ) or G = K k ( K n - 2 k + K ¯ k ) .

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

On-line ranking number for cycles and paths

Erik Bruoth, Mirko Horňák (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A k-ranking of a graph G is a colouring φ:V(G) → 1,...,k such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number χ * r ( G ) of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that χ * r ( P ) < 3 l o g n for n ≥ 2....

The classification of finite groups by using iteration digraphs

Uzma Ahmad, Muqadas Moeen (2016)

Czechoslovak Mathematical Journal

Similarity:

A digraph is associated with a finite group by utilizing the power map f : G G defined by f ( x ) = x k for all x G , where k is a fixed natural number. It is denoted by γ G ( n , k ) . In this paper, the generalized quaternion and 2 -groups are studied. The height structure is discussed for the generalized quaternion. The necessary and sufficient conditions on a power digraph of a 2 -group are determined for a 2 -group to be a generalized quaternion group. Further, the classification of two generated 2 -groups as abelian...

Sum labellings of cycle hypergraphs

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A hypergraph is a sum hypergraph iff there are a finite S ⊆ IN⁺ and d̲, [d̅] ∈ IN⁺ with 1 < d̲ ≤ [d̅] such that is isomorphic to the hypergraph d ̲ , [ d ̅ ] ( S ) = ( V , ) where V = S and = e S : d ̲ | e | [ d ̅ ] v e v S . For an arbitrary hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices y , . . . , y σ V such that y , . . . , y σ is a sum hypergraph. Generalizing the graph Cₙ we obtain d-uniform hypergraphs where any d consecutive vertices of Cₙ form an edge. We determine sum numbers and investigate properties of sum labellings...

Piecewise linear approximation of smooth functions of two variables

Joseph H.G. Fu (2013)

Actes des rencontres du CIRM

Similarity:

The normal cycle of a singular subset X of a smooth manifold is a basic tool for understanding and computing the curvature of X . If X is replaced by a singular function on n then there is a natural companion notion called the of f , which has been introduced by the author and by R. Jerrard. We discuss a few fundamental facts and open problems about functions f that admit gradient cycles, with particular attention to the first nontrivial dimension n = 2 .

Decompositions of nearly complete digraphs into t isomorphic parts

Mariusz Meszka, Zdzisław Skupień (2009)

Discussiones Mathematicae Graph Theory

Similarity:

An arc decomposition of the complete digraph Kₙ into t isomorphic subdigraphs is generalized to the case where the numerical divisibility condition is not satisfied. Two sets of nearly tth parts are constructively proved to be nonempty. These are the floor tth class ( Kₙ-R)/t and the ceiling tth class ( Kₙ+S)/t, where R and S comprise (possibly copies of) arcs whose number is the smallest possible. The existence of cyclically 1-generated decompositions of Kₙ into cycles C n - 1 and into paths...

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