Solving the kernel perfect problem by (simple) forbidden subdigraphs for digraphs in some families of generalized tournaments and generalized bipartite tournaments [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 A digraph such that every proper induced subdigraph has a kernel is said to be \emph{kernel perfect} (KP for short) (\emph{critical kernel imperfect} (CKI for short) resp.) if the digraph has a kernel (does not have a kernel resp.).
H. Galeana-Sánchez, M. Olsen
doaj +3 more sources
Disimplicial arcs, transitive vertices, and disimplicial eliminations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 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.
Martiniano Eguia, Francisco Soulignac
doaj +6 more sources
Relational Galois connections between transitive fuzzy digraphs [PDF]
Mathematical Methods in the Applied Sciences, 2020 Fuzzy-directed graphs are often chosen as the data structure to model and implement solutions to several problems in the applied sciences. Galois connections have also shown to be useful both in theoretical and in practical problems.
Cabrera, Inma P. +4 more
core +5 more sources
Ordered Vertex Partitioning [PDF]
Discrete Mathematics & Theoretical Computer Science, 2000 A transitive orientation of a graph is an orientation of the edges that produces a transitive digraph. The modular decomposition of a graph is a canonical representation of all of its modules.
Ross M. McConnell, Jeremy P. Spinrad
doaj +2 more sources
Action graph of a semigroup act & its functorial connection [PDF]
Categories and General Algebraic Structures with Applications, 2023 In this paper we define C-induced action graph G(S,a,C;A) corresponding to a semigroup act (S,a,A) and a subset C of S. This generalizes many interesting graphs including Cayley Graph of groups and semigroups, Transformation Graphs (TRAG), Group Action ...
Promit Mukherjee +2 more
doaj +1 more source
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 +1 more source
H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs
Discussiones Mathematicae Graph Theory, 2021 Let H be a digraph (possibly with loops) and D a digraph without loops whose arcs are colored with the vertices of H (D is said to be an H-colored digraph). For an arc (x, y) of D, its color is denoted by c(x, y). A directed path W = (v0, . .
Campero-Alonzo José Manuel +1 more
doaj +1 more source
Dual digraphs of finite semidistributive lattices
Cubo, 2022 Dual digraphs of finite join-semidistributive lattices, meet-semidistributive lattices and semidistributive lattices are characterised. The vertices of the dual digraphs are maximal disjoint filter-ideal pairs of the lattice.
Andrew Craig +2 more
doaj +1 more source
$\mathcal F$-hypercyclic and disjoint $\mathcal F$-hypercyclic properties of binary relations over topological spaces [PDF]
Mathematica Bohemica, 2020 We examine various types of $\mathcal F$-hypercyclic ($\mathcal F$-topologically transitive) and disjoint $\mathcal F$-hypercyclic (disjoint $\mathcal F$-topologically transitive) properties of binary relations over topological spaces.
Marko Kostić
doaj +1 more source
Subdegree growth rates of infinite primitive permutation groups [PDF]
, 2006 A transitive group $G$ of permutations of a set $\Omega$ is primitive if the only $G$-invariant equivalence relations on $\Omega$ are the trivial and universal relations.
Smith, Simon M.
core +2 more sources