Results 11 to 20 of about 105 (77)
Signed domination numbers of directed graphs [PDF]
, 2005 summary:The concept of signed domination number of an undirected graph (introduced by J. E. Dunbar, S. T. Hedetniemi, M. A. Henning and P. J. Slater) is transferred to directed graphs. Exact values are found for particular types of tournaments.
Zelinka, Bohdan
core +1 more source
Generalized tournaments and efficient orientations of graphs
, 2021 This thesis is concerned with both theoretical structural results whose possible applications are yet to be determined and algorithmic solutions to mathematical models inspired by real-world problems.
Surmacs, Michel
core
, 1993 In this paper we introduce a generalization of digraphs that are locally tournaments (and hence of tournaments). This is the class of in-tournament digraphs-the set of predecessors of every vertex induces a tournament.
Bangjensen, J., Prisner, E., Huang, J.
core +1 more source
Disjoint cycles of different lengths in graphs and digraphs
, 2017 International audienceIn this paper, we study the question of finding a set of $k$ vertex-disjoint cycles (resp. directed cycles) of distinct lengths in a given graph (resp. digraph).
Harutyunyan, Ararat +4 more
core +2 more sources
Journal of Graph Theory, Volume 110, Issue 1, Page 82-91, September 2025.ABSTRACT An inversion of a tournament T is obtained by reversing the direction of all edges with both endpoints in some set of vertices. Let inv k ( T ) be the minimum length of a sequence of inversions using sets of size at most k that result in the transitive tournament.
Raphael Yuster
wiley +1 more source
Edge‐arc‐disjoint paths in semicomplete mixed graphs
Journal of Graph Theory, Volume 108, Issue 4, Page 705-721, April 2025.Abstract The so‐called weak‐2‐linkage problem asks for a given digraph D=(V,A) $D=(V,A)$ and distinct vertices s1,s2,t1,t2 ${s}_{1},{s}_{2},{t}_{1},{t}_{2}$ of D $D$ whether D $D$ has arc‐disjoint paths P1,P2 ${P}_{1},{P}_{2}$ so that Pi ${P}_{i}$ is an (si,ti) $({s}_{i},{t}_{i})$‐path for i=1,2 $i=1,2$. This problem is NP‐complete for general digraphs
J. Bang‐Jensen, Y. Wang
wiley +1 more source
Hardness of subgraph and supergraph problems in c-tournaments
, 2011 Problems like the directed feedback vertex set problem have much better algorithms in tournaments when compared to general graphs. This motivates us to study a natural generalization of tournaments, named c-tournaments, and see if the structural ...
Kanthi Kiran, S. +3 more
core +1 more source
Strong arc decompositions of split digraphs
Journal of Graph Theory, Volume 108, Issue 1, Page 5-26, January 2025.Abstract A strong arc decomposition of a digraph D = ( V , A ) is a partition of its arc set A into two sets A 1 , A 2 such that the digraph D i = ( V , A i ) is strong for i = 1 , 2. Bang‐Jensen and Yeo conjectured that there is some K such that every K‐arc‐strong digraph has a strong arc decomposition. They also proved that with one exception on four
Jørgen Bang‐Jensen, Yun Wang
wiley +1 more source
Seymour's second neighbourhood conjecture: random graphs and reductions
Random Structures &Algorithms, Volume 66, Issue 1, January 2025.Abstract A longstanding conjecture of Seymour states that in every oriented graph there is a vertex whose second outneighbourhood is at least as large as its outneighbourhood. In this short note we show that, for any fixed p∈[0,1/2)$$ p\in \left[0,1/2\right) $$, a.a.s.
Alberto Espuny Díaz +3 more
wiley +1 more source
, 2017 International audienceThe dichromatic number χ(D) of a digraph D is the least number k such that the vertex set of D can be partitioned into k parts each of which induces an acyclic subdigraph.
Ararat Harutyunyan +5 more
core +1 more source