1. Nut graphs with a prescribed number of vertex and edge orbitsNino Bašić, Ivan Damnjanović, 2026, original scientific article Abstract: A nut graph is a nontrivial graph whose adjacency matrix has a one-dimensional null space spanned by a vector without zero entries. Recently, it was shown that a nut graph has more edge orbits than vertex orbits. It was also shown that for any even $r \geq 2$ and any $k \geq r + 1$, there exist infinitely many nut graphs with r vertex orbits and k edge orbits. Here, we extend this result by finding all the pairs $(r, k)$ for which there exists a nut graph with $r$ vertex orbits and $k$ edge orbits. In particular, we show that for any $k \geq 2$, there are infinitely many Cayley nut graphs with $k$ edge orbits and $k$ arc orbits.
Keywords: nut graph, vertex orbit, edge orbit, arc orbit, Cayley graph, automorphism
Published in RUP: 09.01.2026; Views: 222; Downloads: 5
 Full text (445,35 KB)
This document has more files! More... |
2. Colour-permuting automorphisms of complete Cayley graphsShirin Alimirzaei, Dave Witte Morris, 2025, original scientific article Abstract: Let G be a (finite or infinite) group, and let KG = Cay(G; G \ {1}) be the complete graph with vertex set G, considered as a Cayley graph of G. Being a Cayley graph, it has a natural edge-colouring by sets of the form {s, s-1} for s in G. We prove that every colour-permuting automorphism of KG is an affine map, unless G is isomoprhic to the direct product of Q8 and B, where Q8 is the quaternion group of order 8, and B is an abelian group, such that b2 is trivial for all b in B.
We also prove (without any restriction on G) that every colour-permuting automorphism of KG is the composition of a group automorphism and a colour-preserving graph automorphism. This was conjectured by D. P. Byrne, M. J. Donner, and T. Q. Sibley in 2013.
Keywords: Cayley graph, automorphism, colour-permuting, complete graphs
Published in RUP: 03.11.2025; Views: 262; Downloads: 1
Full text (453,60 KB) |
3. 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: 369; Downloads: 2
Full text (385,94 KB) |
4. 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: 347; Downloads: 0
Full text (431,19 KB) |
5. Distance-regular Cayley graphs over ℤpˢ ⊕ ℤpXiongfeng Zhan, Lu Lu, Xueyi Huang, 2025, original scientific article Abstract: In 2007, Miklavič and Potočnik proposed the problem of characterizing distance-regular Cayley graphs, which can be viewed as an extension of the problem of identifying strongly regular Cayley graphs, or equivalently, regular partial difference sets. Let p be an odd prime. In this paper, all distance-regular Cayley graphs over ℤps ⊕ ℤp are identified. It is shown that every such graph is isomorphic to a complete graph, a complete multipartite graph, or the line graph of a transversal design TD(r, p) with 2 ≤ r ≤ p − 1.
Keywords: distance-regular graph, Cayley graph, Schur ring, Fourier transformation, transversal design
Published in RUP: 21.10.2025; Views: 384; Downloads: 2
Full text (461,23 KB) |
6. On regular graphs with Šoltés verticesNino Bašić, Martin Knor, Riste Škrekovski, 2025, original scientific article Abstract: Let ▫$W(G)$▫ be the Wiener index of a graph ▫$G$▫. We say that a vertex ▫$v \in V(G)$▫ is a Šoltés vertex in ▫$G$▫ if ▫$W(G - v) = W(G)$▫, i.e. the Wiener index does not change if the vertex ▫$v$▫ is removed. In 1991, Šoltés posed the problem of identifying all connected graphs ▫$G$▫ with the property that all vertices of ▫$G$▫ are Šoltés vertices. The only such graph known to this day is ▫$C_{11}$▫. As the original problem appears to be too challenging, several relaxations were studied: one may look for graphs with at least ▫$k$▫ Šoltés vertices; or one may look for ▫$\alpha$▫-Šoltés graphs, i.e. graphs where the ratio between the number of Šoltés vertices and the order of the graph is at least ▫$\alpha$▫. Note that the original problem is, in fact, to find all ▫$1$▫-Šoltés graphs. We intuitively believe that every ▫$1$▫-Šoltés graph has to be regular and has to possess a high degree of symmetry. Therefore, we are interested in regular graphs that contain one or more Šoltés vertices. In this paper, we present several partial results. For every ▫$r\ge 1$▫ we describe a construction of an infinite family of cubic ▫$2$▫-connected graphs with at least ▫$2^r$▫ Šoltés vertices. Moreover, we report that a computer search on publicly available collections of vertex-transitive graphs did not reveal any ▫$1$▫-Šoltés graph. We are only able to provide examples of large ▫$\frac{1}{3}$▫-Šoltés graphs that are obtained by truncating certain cubic vertex-transitive graphs. This leads us to believe that no ▫$1$▫-Šoltés graph other than ▫$C_{11}$▫ exists.
Keywords: Šoltés problem, Wiener index, regular graphs, cubic graphs, Cayley graph, Šoltés vertex
Published in RUP: 10.09.2025; Views: 406; Downloads: 2
Full text (456,75 KB) |
7. |
8. |
9. Cyclic m-DCI-groups and m-CI-groupsIstván Kovács, Luka Šinkovec, 2025, original scientific article Abstract: Based on the earlier work of Li from 1997 and Dobson from 2008, in this paper we complete the classification of cyclic m-DCI-groups and m-CI-groups. For a positive integer m such that m ≥ 3, we show that the group ℤ_(n) is an m-DCI-group if and only if n is not divisible by 8 nor by p² for any odd prime p < m. Furthermore, if m ≥ 6, then we show that ℤn is an m-CI-group if and only if either n ∈ {8, 9, 18}, or n ∉ {8, 9, 18} and n is not divisible by 8 nor by p² for any odd prime p < (m - 1)/2.
Keywords: Cayley graph, cyclic group, m-CI-group, m-DCI-group
Published in RUP: 01.04.2025; Views: 1238; Downloads: 12
Full text (446,08 KB)
This document has more files! More... |
10. Posplošitev Lijeve domneve in popolna klasifikacija cikličnih m-(D)CI-grup : magistrsko deloLuka Šinkovec, 2023, master's thesis Keywords: (un)directed Cayley graph, cyclic group, (un)directed circulant graph, Cayley isomorphism, (un)directed CI-graph, (D)CI-group, m-(D)CI-group, key, generalised multiplier
Published in RUP: 11.09.2023; Views: 2094; Downloads: 30
Full text (520,27 KB) |
