41. 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: 351; Downloads: 1
 Full text (461,23 KB) |
42. 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: 335; Downloads: 1
Full text (398,19 KB) |
43. Monoid algebras and graph productsWilfried Imrich, Igor Klep, Daniel Smertnig, 2025, original scientific article Abstract: In this note, we extend results about unique n^th roots and cancellation of finite disconnected graphs with respect to the Cartesian, the strong and the direct product, to the rooted hierarchical products, and to a modified lexicographic product. We show that these results also hold for graphs with countably many finite connected components, as long as every connected component appears only finitely often (up to isomorphism). The proofs are via monoid algebras and generalized power series rings.
Keywords: graph products, monoid algebras, power series rings, uniqueness of roots, cancellation property
Published in RUP: 21.10.2025; Views: 283; Downloads: 3
Full text (441,50 KB) |
44. |
45. |
46. Planarity testing algorithms : zaključna nalogaUroš Babić, 2025, undergraduate thesis Keywords: graph planarity, planarity testing, Boyer–Myrvold algorithm, Kuratowski/Wagner theorem, depth-first search (DFS), lowpoint values, articulation points, biconnected components, graph embedding, graph6 format
Published in RUP: 04.10.2025; Views: 290; Downloads: 0 |
47. Polycyclic geometric realizations of the Gray configurationLeah Berman, Gábor Gévay, Tomaž Pisanski, 2025, original scientific article Abstract: The Gray configuration is a (27_3) configuration which typically is realized as the points and lines of the 3×3×3 integer lattice. It occurs as a member of an infinite family of configurations defined by Bouwer in 1972. Since their discovery, both the Gray configuration and its Levi graph (i.e., its point-line incidence graph) have been the subject of intensive study. Its automorphism group contains cyclic subgroups isomorphic to Z3 and Z9, so it is natural to ask whether the Gray configuration can be realized in the plane with any of the corresponding rotational symmetry. In this paper, we show that there are two distinct polycyclic realizations with Z3 symmetry. In contrast, the only geometric polycyclic realization with straight lines and Z9 symmetry is only a “weak” realization, with extra unwanted incidences (in particular, the realization is actually a (27_4) configuration).
Keywords: Gray graph, Gray configuration, polycirculant, polycyclic configuration
Published in RUP: 29.09.2025; Views: 426; Downloads: 4
Full text (2,95 MB) |
48. Answers to questions about medial layer graphs of self-dual regular and chiral polytopesMarston Conder, Isabelle Steinmann, 2025, original scientific article Abstract: An abstract n-polytope P is a partially-ordered set which captures important properties of a geometric polytope, for any dimension n. For even n ≥ 2, the incidences between elements in the middle two layers of the Hasse diagram of P give rise to the medial layer graph of P, denoted by G = G(P). If n = 4, and P is both highly symmetric and self-dual of type {p, q, p}, then a Cayley graph C covering G can be constructed on a group of polarities of P. In this paper we address some open questions about the relationship between G and C that were raised in a 2008 paper by Monson and Weiss, and describe some interesting examples of these graphs. In particular, we give the first known examples of improperly self-dual chiral polytopes of type {3, q, 3}, which are also among the very few known examples of highly symmetric self-dual finite polytopes that do not admit a polarity. Also we show that if p = 3 then C cannot have a higher degree of s-arc-transitivity than G, and we present a family of regular 4-polytopes of type {6, q, 6} for which the vertex-stabilisers in the automorphism group of C are larger than those for G.
Keywords: abstract polytope, regular polytope, chiral polytope, medial graph
Published in RUP: 16.09.2025; Views: 344; Downloads: 14
Full text (576,38 KB)
This document has more files! More... |
49. |
50. |
