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: 241; Downloads: 5
 Full text (445,35 KB)
This document has more files! More... |
2. Transitive regular q-analogs of graphsDean Crnković, Vedrana Mikulić Crnković, Andrea Švob, Matea Zubović Žutolija, 2025, original scientific article Abstract: In 1976, Delsarte introduced the notion of q-analogs of designs, and q-analogs of graphs were introduced recently by M. Braun et al. In this paper, we extend that study by giving a method for constructing transitive regular q-analogs of graphs. Further, we illustrate the method by giving some examples. Additionally, we introduced the notion of q-analogs of quasi-strongly regular graphs and give examples of transitive q-analogs of quasi-strongly regular graphs coming from spreads.
Keywords: q-ary design, q-ary graph, regular graph, transitive group
Published in RUP: 03.11.2025; Views: 267; Downloads: 1
Full text (382,29 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, original scientific article Abstract: 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.
Keywords: digraph, vertex-primitive, s-arc-transitive, alternating group, symmetric group
Published in RUP: 22.10.2025; Views: 328; Downloads: 1
Full text (397,42 KB) |
4. Basic tetravalent oriented graphs of independent-cycle typeNemanja Poznanović, Cheryl E. Praeger, 2025, original scientific article Abstract: The family OG(4) consisting of graph-group pairs (Γ, G), where Γ is a finite, connected, 4-valent graph admitting a G-vertex-, and G-edge-transitive, but not G-arc-transitive action, has recently been examined using a normal quotient methodology. A subfamily of OG(4) has been identified as ‘basic’, due to the fact that all members of OG(4) are normal covers of at least one basic pair. We provide an explicit classification of those basic pairs (Γ, G) which have at least two independent cyclic G-normal quotients (these are G-normal quotients which are not extendable to a common cyclic normal quotient).
Keywords: half-arc-transitive, vertex-transitive graph, edge-transitive graph, normal cover, cycle graph
Published in RUP: 21.10.2025; Views: 398; Downloads: 1
Full text (398,19 KB) |
5. Symmetries of the Woolly Hat graphsLeah Berman, Sergio Hiroki Koike Quintanar, Elías Mochán, Alejandra Ramos Rivera, Primož Šparl, Steve Wilson, 2024, original scientific article Abstract: A graph is edge-transitive if the natural action of its automorphism group on its edge set is transitive. An automorphism of a graph is semiregular if all of the orbits of the subgroup generated by this automorphism have the same length. While the tetravalent edge-transitive graphs admitting a semiregular automorphism with only one orbit are easy to determine, those that admit a semiregular automorphism with two orbits took a considerable effort and were finally classified in 2012. Of the several possible different "types" of potential tetravalent edge-transitive graphs admitting a semiregular automorphism with three orbits, only one "type" has thus far received no attention. In this paper we focus on this class of graphs, which we call the Woolly Hat graphs. We prove that there are in fact no edge-transitive Woolly Hat graphs and classify the vertex-transitive ones.
Keywords: edge-transitive, vertex-transitive, tricirculant, Woolly Hat graphs
Published in RUP: 10.09.2025; Views: 662; Downloads: 7
Full text (552,80 KB) |
6. Edge-transitive core-free Nest graphsIstván Kovács, 2025, original scientific article Abstract: A finite simple graph Γ is called a Nest graph if it is regular of valency 6 and admits an automorphism ρ with two orbits of the same length such that at least one of the subgraphs induced by these orbits is a cycle. We say that Γ is core-free if no non-trivial subgroup of the group generated by ρ is normal in Aut(Γ). In this paper, we show that, if Γ is edge-transitive and core-free, then it is isomorphic to one of the following graphs: the complement of the Petersen graph, the Hamming graph H(2,4), the Shrikhande graph and a certain normal 2-cover of K_{3,3} by ℤ_2^4.
Keywords: bicirculant, edge-transitive, primitive permutation group
Published in RUP: 10.09.2025; Views: 418; Downloads: 3
Full text (466,20 KB) |
7. On cubic vertex-transitive graphs of given girthEdward Tauscher Dobson, Ademir Hujdurović, Wilfried Imrich, Ronald Ortner, 2025, original scientific article Abstract: A set of vertices of a graph is distinguishing if the only automorphism that preserves it is the identity. The minimal size of such sets, if they exist, is the distinguishing cost. The distinguishing costs of vertex transitive cubic graphs are well known if they are 1-arc-transitive, or if they have two edge orbits and either have girth 3 or vertex-stabilizers of order 1 or 2. There are many results about vertex-transitive cubic graphs of girth 4 with two edge orbits, but for larger girth almost nothing is known about the distinguishing costs of such graphs. We prove that cubic vertex-transitive graphs of girth 5 with two edge orbits have distinguishing cost 2, and prove the non-existence of infinite 3-arc-transitive cubic graphs of girth 6.
Keywords: distinguishing number, distinguishing cost, vertex-transitive cubic graphs, automorphisms
Published in RUP: 27.08.2025; Views: 774; Downloads: 4
Full text (451,52 KB)
This document has more files! More... |
8. |
9. |
10. The core of a vertex-transitive complementary prismMarko Orel, 2023, original scientific article Abstract: The complementary prism ▫$\Gamma \overline{\Gamma}$▫ is obtained from the union of a graph ▫$\Gamma$▫ and its complement ▫$\overline{\Gamma}$▫ where each pair of identical vertices in ▫$\Gamma$▫ and ▫$\overline{\Gamma}$▫ is joined by an edge. It generalizes the Petersen graph, which is the complementary prism of the pentagon. The core of a vertex-transitive complementary prism is studied. In particular, it is shown that a vertex-transitive complementary prism ▫$\Gamma \overline{\Gamma}$▫ is a core, i.e. all its endomorphisms are automorphisms, whenever ▫$\Gamma$▫ is a core or its core is a complete graph.
Keywords: graph homomorphism, complementary prism, self-complementary graph, vertex-transitive graph, core
Published in RUP: 06.11.2023; Views: 2548; Downloads: 13
Full text (305,54 KB) |
