21. |
22. |
23. |
24. The extremal generalised Randić index for a given degree rangeJohn Haslegrave, 2025, original scientific article Abstract: O and Shi proved that the Randić index of any graph G with minimum degree at least δ and maximum degree at most Δ is at least sqrt(δΔ)/(δ+Δ) |G|, with equality if and only if the graph is (δ, Δ)-biregular. In this note we give a short proof via a more general statement. As an application of our more general result, we classify for any given degree range which graphs minimise (or maximise) the generalised Randić index for any exponent, and describe the transitions between different types of behaviour precisely.
Keywords: Randić index, bounded-degree graph, extremal problem
Published in RUP: 03.11.2025; Views: 283; Downloads: 1
 Full text (403,78 KB) |
25. 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: 245; Downloads: 0
Full text (478,50 KB) |
26. Reinforcement learning for graph theory, II. Small Ramsey numbersMohammad Ghebleh, Salem Al-Yakoob, Ali Kanso, Dragan Stevanović, 2025, original scientific article Abstract: We describe here how the recent Wagner’s approach for applying reinforcement learning to construct examples in graph theory can be used in the search for critical graphs for small Ramsey numbers. We illustrate this application by providing lower bounds for the small Ramsey numbers R(K_{2, 5}, K_{3, 5}), R(B₃, B₆) and R(B₄, B₅) and by improving the lower known bound for R(W₅, W₇).
Keywords: Ramsey number, critical graph, reinforcement learning, cross-entropy method
Published in RUP: 03.11.2025; Views: 248; Downloads: 4
Full text (291,40 KB) |
27. 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: 230; Downloads: 1
Full text (382,29 KB) |
28. 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: 231; Downloads: 1
Full text (453,60 KB) |
29. On asymmetric colourings of graphs with bounded degrees and infinite motionFlorian Lehner, Monika Pilśniak, Marcin Stawiski, 2025, original scientific article Abstract: A vertex colouring of a graph is called asymmetric if the only automorphism which preserves it is the identity. Tucker conjectured that if every automorphism of a connected, locally finite graph moves infinitely many vertices, then there is an asymmetric colouring with 2 colours. This conjecture was recently confirmed by Babai, using the heavy machinery of the classification of finite simple groups. We make progress towards a purely combinatorial proof of this conjecture in the special case of graphs with bounded maximal degree. More precisely, using only elementary combinatorial methods, we prove that if every automorphism of a connected graph with maximal degree Δ moves infinitely many vertices, then there is an asymmetric colouring using O(\sqrt(Δ) log(Δ)) colours. This is the first improvement which does not depend on the classification of finite simple groups over the trivial bound of O(Δ).
Keywords: infinite graph, asymmetric colouring, infinite motion
Published in RUP: 22.10.2025; Views: 316; Downloads: 3
Full text (299,41 KB) |
30. On edge-girth-regular graphs: lower bounds and new familiesIstván Porupsánszki, 2025, original scientific article Abstract: An edge-girth-regular graph egr(n, k, g, λ) is a k-regular graph of order n, girth g and with the property that each of its edges is contained in exactly λ distinct g-cycles. We present new families of edge-girth regular graphs arising from generalized quadrangles and pencils of elliptic quadrics.
An egr(n, k, g, λ) is called extremal for the triple (k, g, λ) if n is the smallest order of any egr(n, k, g, λ). We give new lower bounds for the order of extremal edge-girth-regular graphs using properties of the eigenvalues of the adjacency matrix of a graph.
Keywords: cage problem, extremal graph theory, generalized polygons, ovoids
Published in RUP: 22.10.2025; Views: 341; Downloads: 1
Full text (358,49 KB) |
