1. On the wreath product of signed and gain graphs and its spectrumMatteo Cavaleri, Alfredo Donno, Stefano Spessato, 2025, original scientific article Abstract: 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.
Keywords: gain graph, signed graph, wreath product of graphs, wreath product of groups, circulant gain graph, mixed Kronecker product, π-spectrum
Published in RUP: 22.10.2025; Views: 144; Downloads: 2
 Full text (492,42 KB) |
2. Vertex-transitive graphs and their arc-typesMarston D. E. Conder, Tomaž Pisanski, Arjana Žitnik, 2017, original scientific article Abstract: Let ▫$X$▫ be a finite vertex-transitive graph of valency ▫$d$▫, and let ▫$A$▫ be the full automorphism group of ▫$X$▫. Then the arc-type of ▫$X$▫ is defined in terms of the sizes of the orbits of the stabiliser ▫$A_v$▫ of a given vertex ▫$v$▫ on the set of arcs incident with ▫$v$▫. Such an orbit is said to be self-paired if it is contained in an orbit ▫$\Delta$▫ of ▫$A$▫ on the set of all arcs of v$X$▫ such that v$\Delta$▫ is closed under arc-reversal. The arc-type of ▫$X$▫ is then the partition of ▫$d$▫ as the sum ▫$n_1 + n_2 + \dots + n_t + (m_1 + m_1) + (m_2 + m_2) + \dots + (m_s + m_s)$▫, where ▫$n_1, n_2, \dots, n_t$▫ are the sizes of the self-paired orbits, and ▫$m_1,m_1, m_2,m_2, \dots, m_s,m_s$▫ are the sizes of the non-self-paired orbits, in descending order. In this paper, we find the arc-types of several families of graphs. Also we show that the arc-type of a Cartesian product of two "relatively prime" graphs is the natural sum of their arc-types. Then using these observations, we show that with the exception of ▫$1+1$▫ and ▫$(1+1)$▫, every partition as defined above is \emph{realisable}, in the sense that there exists at least one vertex-transitive graph with the given partition as its arc-type.
Keywords: symmetry type, vertex-transitive graph, arc-transitive graph, Cayley graph, cartesian product, covering graph
Published in RUP: 03.01.2022; Views: 2633; Downloads: 24
Full text (475,17 KB) |
3. |
4. |
5. Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphsDidem Gozüpek, Ademir Hujdurović, Martin Milanič, 2017, original scientific article Keywords: lekisikografski product grafov, minimalna dominantna množica, dobro dominiran graf, nesvodljiva dominantna množica, lexicographic product of graphs, minimal dominating set, well-dominated graph, irreducible dominating set
Published in RUP: 14.11.2017; Views: 3446; Downloads: 68
 Link to full text |
6. Nove karakterizacije v strukturni teoriji grafov : 1-popolno usmerljivi grafi, produktni grafi in cena povezanostiTatiana Romina Hartinger, 2017, doctoral dissertation Keywords: 1-perfectly orientable graph, structural characterization of families of graphs, chordal graph, interval graph, circular arc graph, cograph, block-cactus graph, cobipartite graph, K4-minor-free graph, outerplanar graph, graph product, Cartesian product, lexicographic product, direct product, strong product, price of connectivity, cycle transversal, path transversal
Published in RUP: 09.11.2017; Views: 5128; Downloads: 44
Link to full text |
7. On the split structure of lifted groupsAleksander Malnič, Rok Požar, 2016, original scientific article Abstract: Let ▫$\wp \colon \tilde{X} \to X$▫ be a regular covering projection of connected graphs with the group of covering transformations ▫$\rm{CT}_\wp$▫ being abelian. Assuming that a group of automorphisms ▫$G \le \rm{Aut} X$▫ lifts along $\wp$ to a group ▫$\tilde{G} \le \rm{Aut} \tilde{X}$▫, the problem whether the corresponding exact sequence ▫$\rm{id} \to \rm{CT}_\wp \to \tilde{G} \to G \to \rm{id}$▫ splits is analyzed in detail in terms of a Cayley voltage assignment that reconstructs the projection up to equivalence. In the above combinatorial setting the extension is given only implicitly: neither ▫$\tilde{G}$▫ nor the action ▫$G\to \rm{Aut} \rm{CT}_\wp$▫ nor a 2-cocycle ▫$G \times G \to \rm{CT}_\wp$▫, are given. Explicitly constructing the cover ▫$\tilde{X}$▫ together with ▫$\rm{CT}_\wp$▫ and ▫$\tilde{G}$▫ as permutation groups on ▫$\tilde{X}$▫ is time and space consuming whenever ▫$\rm{CT}_\wp$▫ is large; thus, using the implemented algorithms (for instance, HasComplement in Magma) is far from optimal. Instead, we show that the minimal required information about the action and the 2-cocycle can be effectively decoded directly from voltages (without explicitly constructing the cover and the lifted group); one could then use the standard method by reducing the problem to solving a linear system of equations over the integers. However, along these lines we here take a slightly different approach which even does not require any knowledge of cohomology. Time and space complexity are formally analyzed whenever ▫$\rm{CT}_\wp$▫ is elementary abelian.
Keywords: algorithm, abelian cover, Cayley voltages, covering projection, graph, group extension, group presentation, lifting automorphisms, linear systems over the integers, semidirect product
Published in RUP: 15.10.2015; Views: 4199; Downloads: 170
Full text (422,56 KB) |
8. |
