1. A classification of Q-polynomial distance-regular graphs with girth 6Štefko Miklavič, 2025, original scientific article Abstract: Let Γ denote a Q-polynomial distance-regular graph with diameter D and valency k≥3. In [Homotopy in Q-polynomial distance-regular graphs, Discrete Math., {\bf 223} (2000), 189–206], H. Lewis showed that the girth of Γ is at most 6. In this paper we classify graphs that attain this upper bound. We show that Γ has girth 6 if and only if it is either isomorphic to the Odd graph on a set of cardinality 2D+1, or to a generalized hexagon of order (1,k−1).
Keywords: distance-regular graphs, Q-polynomial property, girth
Published in RUP: 01.12.2025; Views: 1268; Downloads: 3
 Full text (291,61 KB)
This document has more files! More... |
2. A unified Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groupsJ. Pascal Gollin, Kevin Hendrey, O-joung Kwon, Sang-il Oum, Youngho Yoo, 2025, original scientific article Abstract: In 1965, Erdős and Pósa proved that there is an (approximate) duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold for odd cycles, and Dejter and Neumann-Lara asked in 1988 to find all pairs (l, z) of integers where such a duality holds for the family of cycles of length l modulo z. We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface.
Keywords: Erdős-Pósa property, cycle packing, group-labelled graph
Published in RUP: 17.11.2025; Views: 403; Downloads: 8
Full text (1,17 MB)
This document has more files! More... |
3. Groups with elements of order 8 do not have the DCI propertyTed Dobson, Joy Morris, Pablo Spiga, 2025, original scientific article Abstract: Let k be odd, and n an odd multiple of 3. Although this can also be deduced from known results, we provide a new proof that Ck ⋊ C₈ and (Cn × C₃) ⋊ C₈ do not have the Directed Cayley Isomorphism (DCI) property. When k is prime, Ck ⋊ C₈ had previously been proved to have the Cayley Isomorphism (CI) property. To the best of our knowledge, the groups Cp ⋊ C₈ (where p is an odd prime) are only the second known infinite family of groups that have the CI property but do not have the DCI property. This also provides a new proof of the result (which follows from known results but was not explicitly published) that no group with an element of order 8 has the DCI property.
One piece of our proof is a new result that may prove to be of independent interest: we show that if a permutation group has a regular subgroup of index 2 then it must be 2-closed.
Keywords: CI property, DCI property, Cayley graphs, Cayley digraphs, 2-closed groups, 2-closure
Published in RUP: 03.11.2025; Views: 296; Downloads: 1
Full text (344,18 KB) |
4. On a generalization of median graphs: k-median graphsMarc Hellmuth, Sandhya Thekkumpadan Puthiyaveedu, 2025, original scientific article Abstract: Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. To be more formal, a graph G is a median graph if, for all μ, u, v ∈ V(G), it holds that |I(μ, u) ∩ I(μ, v) ∩ I(u, v)| = 1 where I(x, y) denotes the set of all vertices that lie on shortest paths connecting x and y.
In this paper we are interested in a natural generalization of median graphs, called k-median graphs. A graph G is a k-median graph, if there are k vertices μ1, …, μk ∈ V(G) such that, for all u, v ∈ V(G), it holds that |I(μ_i, u) ∩ I(μ_i, v) ∩ I(u, v)| = 1, 1 ≤ i ≤ k. By definition, every median graph with n vertices is an n-median graph. We provide several characterizations of k-median graphs that, in turn, are used to provide many novel characterizations of median graphs.
Keywords: median graph, convexity, meshed and quadrangle property, modular, interval
Published in RUP: 22.10.2025; Views: 299; Downloads: 0
Full text (520,78 KB) |
5. 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: 332; Downloads: 3
Full text (441,50 KB) |
6. |
7. Strong cliques in diamond-free graphsNina Chiarelli, Berenice Martínez-Barona, Martin Milanič, Jérôme Monnot, Peter Muršič, 2020, original scientific article Keywords: maximal clique, maximal stable set, diamond-free graph, strong clique, simplicial clique, strongly perfect graph, CIS graph, NP-hard problem, polynomial-time algorithm, Erdős-Hajnal property
Published in RUP: 17.12.2020; Views: 3885; Downloads: 162
 Link to full text |
8. Strong cliques in diamond-free graphsNina Chiarelli, Berenice Martínez-Barona, Martin Milanič, Jérôme Monnot, Peter Muršič, 2020, published scientific conference contribution Keywords: maximal clique, maximal stable set, diamond-free graph, strong clique, simplicial clique, CIS graph, NP-hard problem, linear-time algorithm, Erdős-Hajnal property
Published in RUP: 10.11.2020; Views: 3298; Downloads: 60
Link to full text |
9. |
10. |
