1. Nut digraphsNino Bašić, Patrick W. Fowler, Maxine M. McCarthy, Primož Potočnik, 2026, original scientific article Abstract: A nut graph is a simple graph whose kernel is spanned by a single full vector (i.e., the adjacency matrix has a single zero eigenvalue and all non-zero kernel eigenvectors have no zero entry). We classify generalisations of nut graphs to nut digraphs: a digraph whose kernel (resp. co-kernel) is spanned by a full vector is dextro-nut (resp. laevo-nut); a bi-nut digraph is both laevo- and dextro-nut; an ambi-nut digraph is a bi-nut digraph where kernel and co-kernel are spanned by the same vector; a digraph is inter-nut if the intersection of the kernel and co-kernel is spanned by a full vector. It is known that a nut graph is connected, leafless and non-bipartite. It is shown here that an ambi-nut digraph is strongly connected, non-bipartite (i.e., has a non-bipartite underlying graph) and has minimum in-degree and minimum out-degree of at least 2. Refined notions of core and core-forbidden vertices apply to singular digraphs. Infinite families of nut digraphs and systematic coalescence, crossover and multiplier constructions are introduced. Relevance of nut digraphs to topological physics is discussed.
Keywords: nut graph, core graph, nullity, directed graph, nut digraph, dextro-nut, laevo-nut, bi-nut, ambi-nut, inter-nut, dextro-core vertex, laevo-core vertex, graph spectra
Published in RUP: 09.01.2026; Views: 237; Downloads: 9
 Full text (873,25 KB)
This document has more files! More... |
2. In-domatic number and some operations in digraphsGermán Benítez-Bobadilla, Laura Pastrana-Ramírez, 2026, original scientific article Abstract: Let D be a digraph, a subset S of V(D) is called in-dominating set in D if for each vertex x ∈ V(D) \ S there is a vertex w ∈ S such that (x, w) ∈ A(D). An in-domatic partition of D is a partition of V(D) where all parts are in-dominating sets in D. The maximum number of parts of an in-domatic partition of D is the in-domatic number of D and it is denoted by d⁻(D). In this work, the in-domatic number for some families of digraphs such as complete digraphs, transitive digraphs, directed cycles and the cartesian product of two cycles, is calculated. Also, in-domatically critical digraphs are characterized. Additionally, the in-domatic partitions of the line digraph and some other operations which reflect the adjacency and incidence relations in digraphs are explored.
Keywords: in-domatic number, in-domatically critical digraph, line digraph, in-domatically full digraph, cartesian product
Published in RUP: 21.12.2025; Views: 271; Downloads: 2
Full text (420,14 KB) |
3. Bounding s for vertex-primitive s-arc-transitive digraphs of alternating and symmetric groupsJunyan Chen, Lei Chen, Michael Giudici, Jing Jian Li, Cheryl E. Praeger, Binzhou Xia, 2025, original scientific article Abstract: Determining an upper bound on s for finite vertex-primitive s-arc-transitive digraphs has received considerable attention dating back to a question of Praeger in 1990. It was shown by Giudici and Xia that the smallest upper bound on s is attained for some digraph admitting an almost simple s-arc-transitive group. In this paper, based on the work of Pan, Wu and Yin, we prove that s<=2 in the case where the group is an alternating or symmetric group.
Keywords: digraph, vertex-primitive, s-arc-transitive, alternating group, symmetric group
Published in RUP: 22.10.2025; Views: 363; Downloads: 2
Full text (397,42 KB) |
4. Coverings of general digraphsAleksander Malnič, Boris Zgrablić, 2025, original scientific article Abstract: A unified theory of covering projections of graphs and digraphs is presented as one theory by considering coverings of general digraphs, where multiple directed and undirected edges together with oriented and unoriented loops and semiedges, are allowed. It transpires that coverings of general digraphs can display certain pathological behaviour since the naturally defined projections of their underlying graphs may not be coverings in the usual topological sense. Consequently, homotopy does not always lift, although the unique walk lifting property still holds. Yet, it is still possible to grasp such coverings algebraically in terms of the action of the fundamental monoid. This action is permutational and has certain nice properties that monoid actions in general do not have. As a consequence, such projections can be studied combinatorially in terms of voltages. The problem of isomorphism and equivalence, and in particular, the problem of lifting automorphisms, is treated in depth. All known results about covering projections of graphs are simple corollaries of just three general theorems.
Keywords: mixed graph, general digraph, dart, covering projection, voltage, homotopy, monoid action, lifting automorphisms
Published in RUP: 10.09.2025; Views: 640; Downloads: 18
Full text (569,42 KB) |
5. Reachability relations, transitive digraphs and groupsAleksander Malnič, Primož Potočnik, Norbert Seifter, Primož Šparl, 2015, original scientific article Abstract: In [A. Malnič, D. Marušič, N. Seifter, P. Šparl and B. Zgrablič, Reachability relations in digraphs, Europ. J. Combin. 29 (2008), 1566-1581] it was shown that properties of digraphs such as growth, property ▫$\mathbf{Z}$▫, and number of ends are reflected by the properties of certain reachability relations defined on the vertices of the corresponding digraphs. In this paper we study these relations in connection with certain properties of automorphism groups of transitive digraphs. In particular, one of the main results shows that if atransitive digraph admits a nilpotent subgroup of automorphisms with finitely many orbits, then its nilpotency class and the number of orbits are closely related to particular properties of reachability relations defined on the digraphs in question. The obtained results have interesting implications for Cayley digraphs of certain types of groups such as torsion-free groups of polynomial growth.
Keywords: Cayley digraph, reachability relation
Published in RUP: 31.12.2021; Views: 2259; Downloads: 20
Full text (311,92 KB) |
6. |
7. |
8. Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theoremAdemir Hujdurović, Martin Milanič, Edin Husić, Romeo Rizzi, Alexandru I. Tomescu, 2017, published scientific conference contribution abstract Keywords: perfect phylogeny, NP-hard problem, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Published in RUP: 17.09.2018; Views: 3967; Downloads: 125
 Link to full text |
9. Reconstructing perfect phylogenies via binary matrices, branchings in DAGs, and a generalization of Dilworth's theoremAdemir Hujdurović, Martin Milanič, Edin Husić, Romeo Rizzi, Alexandru I. Tomescu, 2018, published scientific conference contribution abstract Keywords: perfect phylogeny, NP-hard problem, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Published in RUP: 17.09.2018; Views: 3738; Downloads: 106
Full text (1,44 MB)
This document has more files! More... |
10. Reconstructing perfect phylogenies via binary matrices, branchings in DAGs, and a generalization of Dilworth's theoremMartin Milanič, 2018, published scientific conference contribution abstract (invited lecture) Keywords: perfect phylogeny, NP-hard problem, graph coloring, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Published in RUP: 17.09.2018; Views: 3512; Downloads: 22
Link to full text |
