1. On bipartite (1,1,k)-mixed graphsCristina Dalfó, Grahame Erskine, Geoffrey Exoo, Miquel Àngel Fiol, James Tuite, 2025, izvirni znanstveni članek Opis: Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are bipartite and in which the undirected and directed degrees are one. The best graphs, in terms of the number of vertices, are presented for small diameters. Moreover, two infinite families of such graphs with diameter k and number of vertices of the order of 2k/2 are proposed, one of them being totally regular (1,1)-mixed graphs. In addition, we present two more infinite families called chordal ring and chordal double ring mixed graphs, which are bipartite and related to tessellations of the plane. Finally, we give an upper bound that improves the Moore bound for bipartite mixed graphs for r = z = 1.
Ključne besede: mixed graph, degree/diameter problem, Moore bound, bipartite graph
Objavljeno v RUP: 03.11.2025; Ogledov: 112; Prenosov: 0
 Celotno besedilo (628,98 KB) |
2. On the wreath product of signed and gain graphs and its spectrumMatteo Cavaleri, Alfredo Donno, Stefano Spessato, 2025, izvirni znanstveni članek Opis: We introduce a notion of wreath product of two gain graphs (Γ_1, ψ_1, G_1) and (Γ_2, ψ_2, G_2), producing a gain graph over the direct product group G_2|V_Γ1| × G_1, whose underlying graph is the classical wreath product of graphs Γ_1≀Γ_2. By composition with a suitable group homomorphism, our construction produces a signed graph when the two factors are signed graphs. We prove that the wreath product is stable under switching isomorphism. By using group representations, we are able to perform spectral computations on the wreath product: in particular, we determine its largest and its smallest eigenvalue, and we give a description of the spectrum when the first factor is a complex unit complete balanced or antibalanced gain graph, and the second factor is circulant. Finally, when G_1 is a group of permutations of the vertex set of the first factor, and the group G_2 is abelian, we give an alternative definition producing a gain graph over the group wreath product G_1≀G_2, which turns out to be stable under switching equivalence of the second factor, when the first factor is balanced.
Ključne besede: gain graph, signed graph, wreath product of graphs, wreath product of groups, circulant gain graph, mixed Kronecker product, π-spectrum
Objavljeno v RUP: 22.10.2025; Ogledov: 142; Prenosov: 2
Celotno besedilo (492,42 KB) |
3. 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: 241; Prenosov: 17
Celotno besedilo (569,42 KB) |
