Results 11 to 20 of about 1,150 (71)
Kernels in quasi-transitive digraphs
Discrete Mathematics, 2006 In this paper \(D\) denotes a possibly infinite digraph. A kernel \(N\) of a digraph \(D\) is an independent set of vertices such that for each \(w\in V(D)-N\) there exists an arc from \(w\) to \(N\). A digraph \(D\) is quasi-transitive when \(uv\in A(D)\) and \(vw\in A(D)\) implies that \(uw\in A(D)\) or \(wu\in A(D)\).
Galeana-Sánchez, Hortensia +1 more
openaire +4 more sources
Minimum cycle factors in quasi-transitive digraphs
Discrete Optimization, 2008 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bang-Jensen, Jørgen +1 more
openaire +5 more sources
Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-Transitive Digraphs
, 2007 For digraphs $G$ and $H$, a homomorphism of $G$ to $H$ is a mapping $f:\ V(G)\dom V(H)$ such that $uv\in A(G)$ implies $f(u)f(v)\in A(H)$. If, moreover, each vertex $u \in V(G)$ is associated with costs $c_i(u), i \in V(H)$, then the cost of a homomorphism $f$ is $\sum_{u\in V(G)}c_{f(u)}(u)$.
Gupta, A. +4 more
openaire +5 more sources
Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs
SIAM Journal on Discrete Mathematics, 2003 Summary: We consider the problem of finding a strongly connected spanning subdigraph with the minimum number of arcs in a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamiltonian cycle problem. We show that the problem is polynomially solvable for quasi-transitive digraphs.
Bang-Jensen, J., Huang, J., Yeo, Anders
openaire +11 more sources
A conjecture on 3-anti-quasi-transitive digraphs
Discrete Mathematics, 2014 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Ruixia Wang
openaire +4 more sources
On kernels by rainbow paths in arc-coloured digraphs
Open Mathematics, 2021 In 2018, Bai, Fujita and Zhang [Discrete Math. 341 (2018), no. 6, 1523–1533] introduced the concept of a kernel by rainbow paths (for short, RP-kernel) of an arc-coloured digraph DD, which is a subset SS of vertices of DD such that (aa) there exists no ...
Li Ruijuan, Cao Yanqin, Zhang Xinhong
doaj +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
\(k\)-kernels in \(k\)-transitive and \(k\)-quasi-transitive digraphs
Discrete Mathematics, 2012 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Hernández-Cruz, César +1 more
+6 more sources
Research on Extreme Signed Graphs with Minimal Energy in Tricyclic Signed Graphs S(n, n + 2)
Complexity, Volume 2020, Issue 1, 2020., 2020 A signed graph is acquired by attaching a sign to each edge of a simple graph, and the signed graphs have been widely used as significant computer models in the study of complex systems. The energy of a signed graph S can be described as the sum of the absolute values of its eigenvalues.
Yajing Wang +2 more
wiley +1 more source
Disimplicial arcs, transitive vertices, and disimplicial eliminations [PDF]
, 2014 In this article we deal with the problems of finding the disimplicial arcs of a digraph and recognizing some interesting graph classes defined by their existence.
Eguía, Martiniano +1 more
core +3 more sources