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: 150; Downloads: 5
 Full text (445,35 KB)
This document has more files! More... |
2. On extremal (almost) edge-girth-regular graphsGabriela Araujo-Pardo, György Kiss, István Porupsánszki, 2025, original scientific article Abstract: A k-regular graph of girth g is called an edge-girth-regular graph, or an egr-graph for short, if each of its edges is contained in exactly λ distinct g-cycles. An egr-graph is called extremal for the triple (k, g, λ) if has the smallest possible order. We prove that some graphs arising from incidence graphs of finite planes are extremal egr-graphs. We also prove new lower bounds on the order of egr-graphs.
Keywords: edge-girth-regular graph, cage problem, finite biaffine planes
Published in RUP: 03.11.2025; Views: 315; Downloads: 2
Full text (547,76 KB) |
3. |
4. Primitive, edge-short, isometric, and pantochordal cyclesGover E. C. Guzman, Marcos E. González Laffitte, André Fujita, Peter F. Stadler, 2025, original scientific article Abstract: A cycle in a graph G is said to be primitive from its vertex x if at least one of its edges does not belong to any shorter cycle that passes through x. This type of cycle and an associated notion of extended neighborhoods play a key role in message-passing algorithms that compute spectral properties of graphs with short loops. Here, we investigate such primitive cycles and graphs without long primitive cycles in a more traditional graph-theoretic framework. We show that a cycle is primitive from all its vertices if and only if it is isometric. We call a cycle fully redundant cycles if it is not primitive from any of its vertices and show that fully redundant cycles, in particular, are not edge short, i.e., they cannot be represented as the edge-disjoint union of a single edge and two shortest paths in G. The families Rk and Lk of graphs with all cycles of length at least k + 1 being fully redundant and not edge-short, respectively, coincide for k = 3 and k = 4. In these graphs, all cycles of length at least k + 1 are pantochordal, i.e., each of their vertices is incident with a chord. None of these results generalizes to k ≥ 5. Moreover, R₃ = L₃ turn out to be the block graphs, and R₄ = L₄ are the graphs with complete multi-partite blocks. The cographs, finally, are shown to form a proper subset of R₅.
Keywords: edge-short cycle, chord, block-graph, complete multipartite graph, wheel graphs, cographs, geodesic cycles, Hamiltonian cycles
Published in RUP: 03.11.2025; Views: 239; Downloads: 0
Full text (478,50 KB) |
5. 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: 331; Downloads: 1
Full text (398,19 KB) |
6. Some recent discoveries about half-arc-transitive graphs : dedicated to Dragan Marušič on the occasion of his 60th birthdayMarston D. E. Conder, Primož Potočnik, Primož Šparl, 2015, original scientific article Abstract: We present some new discoveries about graphs that are half-arc-transitive (that is, vertex- and edge-transitive but not arc-transitive). These include the recent discovery of the smallest half-arc-transitive 4-valent graph with vertex-stabiliser of order 4, and the smallest with vertex-stabiliser of order 8, two new half-arc-transitive 4-valent graphs with dihedral vertex-stabiliser ▫$D_4$▫ (of order 8), and the first known half-arc-transitive 4-valent graph with vertex-stabiliser of order 16 that is neither abelian nor dihedral. We also use half-arc-transitive group actions to provide an answer to a recent question of Delorme about 2-arc-transitive digraphs that are not isomorphic to their reverse.
Keywords: graph, edge-transitive, vertex-transitive, arc-transitive, half arc-transitive
Published in RUP: 31.12.2021; Views: 2556; Downloads: 23
Full text (333,06 KB) |
7. |
8. Edge elimination and weighted graph classesJesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Matjaž Krnc, Martin Milanič, Nevena Pivač, Robert Scheffler, Martin Strehler, 2020, published scientific conference contribution Keywords: edge elimination, weighted graph, split graph, threshold graph, chain graph, linear-time recognition algorithm
Published in RUP: 10.11.2020; Views: 3049; Downloads: 38
 Link to full text |
9. Edge elimination schemes of weighted graph classes, Workshop on Graph Modification algorithms, experiments and new problems, 23rd - 24th January 2020, Bergen, NorwayMartin Milanič, Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, Martin Strehler, 2020, unpublished invited conference lecture Keywords: graph class, edge elimination scheme, sandwich monotonicity
Published in RUP: 28.05.2020; Views: 3057; Downloads: 0 |
10. Avoidable vertices and edges in graphsJesse Beisegel, Maria Chudnovsky, Vladimir Gurvich, Martin Milanič, Mary Agnes Milanič, 2019, published scientific conference contribution Keywords: simplicial vertex, avoidable vertex, avoidable edge, avoidable path, maximum weight clique problem, polynomial-time algorithm, hole-cyclically orientable graph
Published in RUP: 20.08.2019; Views: 3644; Downloads: 161
Link to full text |
