1. Nut digraphsNino Bašić, Patrick W. Fowler, Maxine M. McCarthy, Primož Potočnik, 2026, izvirni znanstveni članek Opis: 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.
Ključne besede: 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
Objavljeno v RUP: 09.01.2026; Ogledov: 583; Prenosov: 37
 Celotno besedilo (873,25 KB)
Gradivo ima več datotek! Več... |
2. In-domatic number and some operations in digraphsGermán Benítez-Bobadilla, Laura Pastrana-Ramírez, 2026, izvirni znanstveni članek Opis: 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.
Ključne besede: in-domatic number, in-domatically critical digraph, line digraph, in-domatically full digraph, cartesian product
Objavljeno v RUP: 21.12.2025; Ogledov: 696; Prenosov: 5
Celotno besedilo (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, izvirni znanstveni članek Opis: 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.
Ključne besede: digraph, vertex-primitive, s-arc-transitive, alternating group, symmetric group
Objavljeno v RUP: 22.10.2025; Ogledov: 637; Prenosov: 6
Celotno besedilo (397,42 KB) |
4. Coverings of general digraphsAleksander Malnič, Boris Zgrablić, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: mixed graph, general digraph, dart, covering projection, voltage, homotopy, monoid action, lifting automorphisms
Objavljeno v RUP: 10.09.2025; Ogledov: 1119; Prenosov: 21
Celotno besedilo (569,42 KB) |
5. Reachability relations, transitive digraphs and groupsAleksander Malnič, Primož Potočnik, Norbert Seifter, Primož Šparl, 2015, izvirni znanstveni članek Opis: 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.
Ključne besede: Cayley digraph, reachability relation
Objavljeno v RUP: 31.12.2021; Ogledov: 2587; Prenosov: 22
Celotno besedilo (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, objavljeni povzetek znanstvenega prispevka na konferenci Ključne besede: perfect phylogeny, NP-hard problem, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Objavljeno v RUP: 17.09.2018; Ogledov: 4534; Prenosov: 126
 Povezava na celotno besedilo |
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, objavljeni povzetek znanstvenega prispevka na konferenci Ključne besede: perfect phylogeny, NP-hard problem, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Objavljeno v RUP: 17.09.2018; Ogledov: 4159; Prenosov: 110
Celotno besedilo (1,44 MB)
Gradivo ima več datotek! Več... |
10. Reconstructing perfect phylogenies via binary matrices, branchings in DAGs, and a generalization of Dilworth's theoremMartin Milanič, 2018, objavljeni povzetek znanstvenega prispevka na konferenci (vabljeno predavanje) Ključne besede: perfect phylogeny, NP-hard problem, graph coloring, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Objavljeno v RUP: 17.09.2018; Ogledov: 3998; Prenosov: 23
Povezava na celotno besedilo |
