Cycle-pancyclism in bipartite tournaments II

Hortensia Galeana-Sánchez

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)}) \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 <...

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 (γ) \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...

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 $^{\to} 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 =^{\to} 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.

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

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, \dots 〉$ generated by an involution $a$ and an element $b$ of order $s \geq 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^{\circ}$ and $T^{☆}$ are partial latin squares of order $n$ , with the property that each row and each column of $T^{\circ}$ contains the same set of entries as the corresponding row or column of $T^{☆}$ . In addition, suppose that each cell in $T^{\circ}$ 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^{\circ}, T^{☆})$ forms a . The of $T$ is the total number of filled cells in $T^{\circ}$ (equivalently $T^{☆}$ ). The latin bitrade is if there is no...

On short cycles in triangle-free oriented graphs

Yurong Ji, Shufei Wu, Hui Song (2018)

Czechoslovak Mathematical Journal

Similarity:

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on $n$ vertices with minimum outdegree $d$ contains a directed cycle of length at most $⌈ n / d ⌉$ . In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that $α_{0}$ is the smallest real such that every $n$ -vertex digraph with minimum outdegree at least $α_{0} n$ contains a directed triangle. Let $ϵ < (3 - 2 α_{0}) / (4 - 2 α_{0})$ be a positive real. We show that if $D$ is an oriented graph...

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 \geq 2,$ $n \geq k^{3} + k + 4,$ and let $G$ be a graph of order $n$ , with minimum degree $δ (G) \geq k .$ If $λ (G) \geq n - k - 1,$ then $G$ has a Hamiltonian cycle, unless $G = K_{1} \lor (K_{n - k - 1} + K_{k})$ or $G = K_{k} \lor (K_{n - 2 k} + {\bar{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...

Finding vertex-disjoint cycle cover of undirected graph using the least-squares method

Lamač, Jan, Vlasák, Miloslav

Similarity:

We investigate the properties of the least-squares solution of the system of equations with a matrix being the incidence matrix of a given undirected connected graph $G$ and we propose an algorithm that uses this solution for finding a vertex-disjoint cycle cover (2-factor) of the graph $G$ .

Acyclic 4-choosability of planar graphs without 4-cycles

Yingcai Sun, Min Chen (2020)

Czechoslovak Mathematical Journal

Similarity:

A proper vertex coloring of a graph $G$ is acyclic if there is no bicolored cycle in $G$ . In other words, each cycle of $G$ must be colored with at least three colors. Given a list assignment $L = {L (v) : v \in V}$ , if there exists an acyclic coloring $π$ of $G$ such that $π (v) \in L (v)$ for all $v \in V$ , then we say that $G$ is acyclically $L$ -colorable. If $G$ is acyclically $L$ -colorable for any list assignment $L$ with $| L (v) | \geq k$ for all $v \in V$ , then $G$ is acyclically $k$ -choosable. In 2006, Montassier, Raspaud and Wang conjectured that every planar graph without...

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