31. 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: 385; Downloads: 5
 Full text (492,42 KB) |
32. Mutual-visibility problems in Kneser and Johnson graphsGülnaz Boruzanlı Ekinci, Csilla Bujtás, 2025, original scientific article Abstract: Let G be a connected graph and X ⊆ V(G). By definition, two vertices u and v are X-visible in G if there exists a shortest u, v-path with all internal vertices being outside of the set X. The largest size of X such that any two vertices of G (resp. any two vertices from X) are X-visible is the total mutual-visibility number (resp. the mutual-visibility number) of G.
In this paper, we determine the total mutual-visibility number of Kneser graphs, bipartite Kneser graphs, and Johnson graphs. The formulas proved for Kneser, and bipartite Kneser graphs are related to the size of transversal-critical uniform hypergraphs, while the total mutual-visibility number of Johnson graphs is equal to a hypergraph Turán number. Exact values or estimations for the mutual-visibility number over these graph classes are also established.
Keywords: mutual-visibility set, total mutual-visibility set, Kneser graph, bipartite Kneser graph, Johnson graph, Turán-type problem, covering design
Published in RUP: 22.10.2025; Views: 306; Downloads: 6
Full text (426,16 KB) |
33. On a generalization of median graphs: k-median graphsMarc Hellmuth, Sandhya Thekkumpadan Puthiyaveedu, 2025, original scientific article Abstract: Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. To be more formal, a graph G is a median graph if, for all μ, u, v ∈ V(G), it holds that |I(μ, u) ∩ I(μ, v) ∩ I(u, v)| = 1 where I(x, y) denotes the set of all vertices that lie on shortest paths connecting x and y.
In this paper we are interested in a natural generalization of median graphs, called k-median graphs. A graph G is a k-median graph, if there are k vertices μ1, …, μk ∈ V(G) such that, for all u, v ∈ V(G), it holds that |I(μ_i, u) ∩ I(μ_i, v) ∩ I(u, v)| = 1, 1 ≤ i ≤ k. By definition, every median graph with n vertices is an n-median graph. We provide several characterizations of k-median graphs that, in turn, are used to provide many novel characterizations of median graphs.
Keywords: median graph, convexity, meshed and quadrangle property, modular, interval
Published in RUP: 22.10.2025; Views: 266; Downloads: 0
Full text (520,78 KB) |
34. Minimal directed strongly regular Cayley graphs over generalized dicyclic groupsYueli Han, Lu Lu, 2025, original scientific article Abstract: Let G be a group with identity element 1, and let S be a subset of G \ {1}. The subset S is called minimal if ⟨S⟩ = G and there exists an element s ∈ S such that ⟨S \ {s, s−1}⟩ ≠ G. In this paper, we completely determine all directed strongly regular Cayley graphs Cay(G, S) for any generalized dicyclic group G, provided that S is a minimal subset of G.
Keywords: directed strongly regular graph, Cayley graph, generalized dicyclic group
Published in RUP: 21.10.2025; Views: 344; Downloads: 2
Full text (385,94 KB) |
35. On a conjecture of Erdős on size Ramsey number of star forestsAkbar Davoodi, Ramin Javadi, Azam Kamranian, Ghaffar Raeisi, 2025, original scientific article Abstract: Given two graphs F_1 and F_2, their size Ramsey number, denoted by r̂(F_1, F_2), is the minimum number of edges of a graph G such that for any edge coloring of G by colors red and blue, G contains either a red copy of F1 or a blue copy of F2. In this paper, we deal with the size Ramsey number of star forests (disjoint union of stars) and following a conjecture by Burr, Erdős, Faudree, Rousseau, and Schelp in 1978, we determine the exact value of r̂(⊔_{i = 1}^s K_{1, ni}, ⊔_{i = 1}^t K_{1, mi}) in several cases including when either m_i’s and n_i’s are odd, or s = 1 or s = 2 and n_1 = n_2.
Keywords: size Ramsey number, star forest, Ramsey minimal graph
Published in RUP: 21.10.2025; Views: 310; Downloads: 4
Full text (282,24 KB) |
36. Adjacent vertex distinguishing total coloring of corona product of graphsHanna Furmańczyk, Rita Zuazua, 2025, original scientific article Abstract: An adjacent vertex distinguishing total k-coloring f of a graph G is a proper total k-coloring of G such that no pair of adjacent vertices has the same color sets, where the color set at a vertex v, C_f^G(v), is {f(v)} ∪ {f(vu)|u ∈ V(G), vu ∈ E(G)}. In 2005 Zhang et al. posted the conjecture (AVDTCC) that every simple graph G has adjacent vertex distinguishing total (Δ(G) + 3)-coloring. In this paper we confirm the conjecture for many types of coronas, in particular for generalized, simple and l-coronas of graphs, not relating the results to particular graph classes of the factors.
Keywords: corona graph, l-corona, generalized corona graph, adjacent vertex distinguishing total coloring, AVDTC Conjecture
Published in RUP: 21.10.2025; Views: 296; Downloads: 1
Full text (367,69 KB) |
37. Perfect matching cuts partitioning a graph into complementary subgraphsDiane Castonguay, Erika M. M. Coelho, Hebert Coelho, Julliano R. Nascimento, Uéverton S. Souza, 2025, original scientific article Abstract: In PARTITION INTO COMPLEMENTARY SUBGRAPHS (COMP-SUB) we are given a graph G = (V, E), and an edge set property Π, and asked whether G can be decomposed into two graphs, H and its complement H̄, for some graph H, in such a way that the edge cut [V(H), V(H̄)] satisfies the property Π. Motivated by previous work, we consider COMP-SUB(Π) when the property Π=PM specifies that the edge cut of the decomposition is a perfect matching. We prove that COMP-SUB(PM) is GI-hard when the graph G is C_5-free or G is {C_k ≥ 7, C̄_k ≥ 7}-free. On the other hand, we show that COMP-SUB(PM) is polynomial-time solvable on hole-free graphs and on P5-free graphs. Furthermore, we present characterizations of COMP-SUB(PM) on chordal, distance-hereditary, and extended P_4-laden graphs.
Keywords: graph partitioning, complementary subgraphs, perfect matching, matching cut, graph isomorphism
Published in RUP: 21.10.2025; Views: 331; Downloads: 2
Full text (420,94 KB) |
38. Regular and semi-regular representations of groups by posetsJonathan A. Barmak, 2025, original scientific article Abstract: By a result of Babai, with finitely many exceptions, every group G admits a semi-regular poset representation with three orbits, that is, a poset P with automorphism group Aut(P) ≃ G such that the action of Aut(P) on the underlying set is free and with three orbits. Among finite groups, only the trivial group and ℤ_2 have a regular poset representation (i.e. semi-regular with one orbit), however many infinite groups admit such a representation. In this paper we study non-necessarily finite groups which have a regular representation or a semi-regular representation with two orbits. We prove that if G admits a Cayley graph which is locally the Cayley graph of a free group, then it has a semi-regular representation of height 1 with two orbits. In this case we will see that any extension of the integers by G admits a regular representation. Applications are given to finite simple groups, hyperbolic groups, random groups and indicable groups.
Keywords: automorphism group of posets, Cayley graph, Dehn presentation, simple groups, random groups
Published in RUP: 21.10.2025; Views: 321; Downloads: 0
Full text (431,19 KB) |
39. Upper embeddability of graphs and products of transpositions associated with edgesShuhei Tsujie, Ryo Uchiumi, 2025, original scientific article Abstract: Given a graph, we associate each edge with the transposition which exchanges the endvertices. Fixing a linear order on the edge set, we obtain a permutation of the vertices. Dénes proved that the permutation is a full cyclic permutation for any linear order if and only if the graph is a tree.
In this article, we characterize graphs having a linear order such that the associated permutation is a full cyclic permutation in terms of graph embeddings. Moreover, we give a counter example for Eden's question about an edge ordering whose associated permutation is the identity.
Keywords: full cyclic permutation ordering, upper-embeddable graph, 2-cell embedding, rotation system
Published in RUP: 21.10.2025; Views: 250; Downloads: 0
Full text (324,31 KB) |
40. |
