Results 11 to 20 of about 1,490 (70)
Journal of the London Mathematical Society, Volume 108, Issue 5, Page 1852-1885, November 2023., 2023 Abstract A k$k$‐uniform hypergraph M$M$ is set‐homogeneous if it is countable (possibly finite) and whenever two finite induced subhypergraphs U,V$U,V$ are isomorphic there is g∈Aut(M)$g\in \mathop {\rm Aut}\nolimits (M)$ with Ug=V$U^g=V$; the hypergraph M$M$ is said to be homogeneous if in addition every isomorphism between finite induced ...
Amir Assari +2 more
wiley +1 more source
Complementary cycles of any length in regular bipartite tournaments
Journal of Graph Theory, Volume 103, Issue 2, Page 186-211, June 2023., 2023 Abstract Let D $D$ be a k $k$‐regular bipartite tournament on n $n$ vertices. We show that, for every p $p$ with 2≤p≤n∕2−2 $2\le p\le n\unicode{x02215}2-2$, D $D$ has a cycle C $C$ of length 2p $2p$ such that D\C $D\backslash C$ is Hamiltonian unless D $D$ is isomorphic to the special digraph F4k ${F}_{4k}$.
Stéphane Bessy, Jocelyn Thiebaut
wiley +1 more source
On coloring digraphs with forbidden induced subgraphs
Journal of Graph Theory, Volume 103, Issue 2, Page 323-339, June 2023., 2023 Abstract We prove a conjecture by Aboulker, Charbit, and Naserasr by showing that every oriented graph in which the out‐neighborhood of every vertex induces a transitive tournament can be partitioned into two acyclic induced subdigraphs. We prove multiple extensions of this result to larger classes of digraphs defined by a finite list of forbidden ...
Raphael Steiner
wiley +1 more source
Making a tournament k $k$‐strong
Journal of Graph Theory, Volume 103, Issue 1, Page 5-11, May 2023., 2023 Abstract A digraph is k ${\bf{k}}$‐strong if it has n ≥ k + 1 $n\ge k+1$ vertices and every induced subdigraph on at least n − k + 1 $n-k+1$ vertices is strongly connected. A tournament is a digraph with no pair of nonadjacent vertices. We prove that every tournament on n ≥ k + 1 $n\ge k+1$ vertices can be made k $k$‐strong by adding no more than k ...
Jørgen Bang‐Jensen +2 more
wiley +1 more source
Spanning eulerian subdigraphs in semicomplete digraphs
Journal of Graph Theory, Volume 102, Issue 3, Page 578-606, March 2023., 2023 Abstract A digraph is eulerian if it is connected and every vertex has its in‐degree equal to its out‐degree. Having a spanning eulerian subdigraph is thus a weakening of having a hamiltonian cycle. In this paper, we first characterize the pairs (D,a) $(D,a)$ of a semicomplete digraph D $D$ and an arc a $a$ such that D $D$ has a spanning eulerian ...
Jørgen Bang‐Jensen +2 more
wiley +1 more source
Path decompositions of tournaments
Proceedings of the London Mathematical Society, Volume 126, Issue 2, Page 429-517, February 2023., 2023 Abstract In 1976, Alspach, Mason, and Pullman conjectured that any tournament T$T$ of even order can be decomposed into exactly ex(T)$\operatorname{ex}(T)$ paths, where ex(T)≔12∑v∈V(T)|dT+(v)−dT−(v)|$\operatorname{ex}(T)\coloneqq \frac{1}{2}\sum _{v\in V(T)}|d_T^+(v)-d_T^-(v)|$. We prove this conjecture for all sufficiently large tournaments.
António Girão +4 more
wiley +1 more source
Seymour’s Second Neighborhood Conjecture for m‐Free Oriented Graphs
Mathematical Problems in Engineering, Volume 2022, Issue 1, 2022., 2022 Let (D = (V, E)) be an oriented graph with minimum out‐degree δ+. For x ∈ V(D), let dD+x and dD++x be the out‐degree and second out‐degree of x in D, respectively. For a directed graph D, we say that a vertex x ∈ V(D) is a Seymour vertex if dD++x≥dD+x. Seymour in 1990 conjectured that each oriented graph has a Seymour vertex.
Huawen Ma, Ganesh Ghorai
wiley +1 more source
On the infinite Lucchesi–Younger conjecture I
Journal of Graph Theory, Volume 98, Issue 1, Page 27-48, September 2021., 2021 Abstract A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of an edge set meeting every dicut equals the maximum number of disjoint dicuts in that digraph. In this first paper out of a series of two papers,
J. Pascal Gollin, Karl Heuer
wiley +1 more source
Decomposing tournaments into paths
Proceedings of the London Mathematical Society, Volume 121, Issue 2, Page 426-461, August 2020., 2020 Abstract We consider a generalisation of Kelly's conjecture which is due to Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by Kühn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman asks for the minimum number
Allan Lo +3 more
wiley +1 more source
Vertex‐disjoint properly edge‐colored cycles in edge‐colored complete graphs
Journal of Graph Theory, Volume 94, Issue 3, Page 476-493, July 2020., 2020 Abstract It is conjectured that every edge‐colored complete graph G on n vertices satisfying Δmon(G)≤n−3k+1 contains k vertex‐disjoint properly edge‐colored cycles. We confirm this conjecture for k=2, prove several additional weaker results for general k, and we establish structural properties of possible minimum counterexamples to the conjecture.
Ruonan Li, Hajo Broersma, Shenggui Zhang
wiley +1 more source