Results 1 to 10 of about 1,081 (54)
Hamiltonian Cycle Problem in Strong k-Quasi-Transitive Digraphs With Large Diameter
Discussiones Mathematicae Graph Theory, 2021 Let k be an integer with k ≥ 2. A digraph is k-quasi-transitive, if for any path x0x1... xk of length k, x0 and xk are adjacent. Let D be a strong k-quasi-transitive digraph with even k ≥ 4 and diameter at least k +2.
Wang Ruixia
doaj +3 more sources
On the existence and number of
CoRR, 2013 Let $D=(V(D), A(D))$ be a digraph and $k \ge 2$ an integer. We say that $D$ is $k$-quasi-transitive if for every directed path $(v_0, v_1,..., v_k)$ in $D$, then $(v_0, v_k) \in A(D)$ or $(v_k, v_0) \in A(D)$. Clearly, a 2-quasi-transitive digraph is a quasi-transitive digraph in the usual sense.
Hortensia Galeana‐Sánchez +2 more
core +4 more sources
The structure of strong $k$-quasi-transitive digraphs with large diameters [PDF]
, 2020 15 ...
Ruixia Wang, Hui Zhang
openalex +3 more sources
k‐quasi‐transitive digraphs of large diameter
Journal of Graph Theory, 2020 AbstractGiven an integer with , a digraph is ‐quasi‐transitive if for every ‐directed path of length in , we have or (or both). In this study, we prove that if is an odd integer, , then every strong ‐quasi‐transitive digraph of diameter at least admits a partition of its vertex set such that is Hamiltonian, and both and are semicomplete ...
Jesús Alva‐Samos +1 more
openalex +3 more sources
Discrete Mathematics, 2012 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
César Hernández‐Cruz +1 more
openalex +3 more sources
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
4-Transitive Digraphs I: The Structure of Strong 4-Transitive Digraphs
Discussiones Mathematicae Graph Theory, 2013 Let D be a digraph, V (D) and A(D) will denote the sets of vertices and arcs of D, respectively. A digraph D is transitive if for every three distinct vertices u, v,w ∈ V (D), (u, v), (v,w) ∈ A(D) implies that (u,w) ∈ A(D).
Hernández-Cruz César
doaj +1 more source
, 2015 This is an Open Access article, first published by E-CJ on 25 February 2015.We study digraphs preserved by a Maltsev operation: Maltsev digraphs. We show that these digraphs retract either onto a directed path or to the disjoint union of directed cycles,
Carvalho, Catarina +3 more
core +1 more source
Some Remarks On The Structure Of Strong K-Transitive Digraphs
Discussiones Mathematicae Graph Theory, 2014 A digraph D is k-transitive if the existence of a directed path (v0, v1, . . . , vk), of length k implies that (v0, vk) ∈ A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense.
Hernández-Cruz César +1 more
doaj +1 more source
On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs
Discussiones Mathematicae Graph Theory, 2014 Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V (D) − N there exists v ∈ N such that d(u, v)
Hell Pavol, Hernández-Cruz César
doaj +1 more source