1. A classification of Q-polynomial distance-regular graphs with girth 6Štefko Miklavič, 2025, izvirni znanstveni članek Opis: 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).
Ključne besede: distance-regular graphs, Q-polynomial property, girth
Objavljeno v RUP: 01.12.2025; Ogledov: 1613; Prenosov: 3
 Celotno besedilo (291,61 KB)
Gradivo ima več datotek! Več... |
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, izvirni znanstveni članek Opis: 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.
Ključne besede: Erdős-Pósa property, cycle packing, group-labelled graph
Objavljeno v RUP: 17.11.2025; Ogledov: 470; Prenosov: 8
Celotno besedilo (1,17 MB)
Gradivo ima več datotek! Več... |
3. Groups with elements of order 8 do not have the DCI propertyTed Dobson, Joy Morris, Pablo Spiga, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: CI property, DCI property, Cayley graphs, Cayley digraphs, 2-closed groups, 2-closure
Objavljeno v RUP: 03.11.2025; Ogledov: 344; Prenosov: 2
Celotno besedilo (344,18 KB) |
4. On a generalization of median graphs: k-median graphsMarc Hellmuth, Sandhya Thekkumpadan Puthiyaveedu, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: median graph, convexity, meshed and quadrangle property, modular, interval
Objavljeno v RUP: 22.10.2025; Ogledov: 353; Prenosov: 1
Celotno besedilo (520,78 KB) |
5. Monoid algebras and graph productsWilfried Imrich, Igor Klep, Daniel Smertnig, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: graph products, monoid algebras, power series rings, uniqueness of roots, cancellation property
Objavljeno v RUP: 21.10.2025; Ogledov: 386; Prenosov: 4
Celotno besedilo (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, izvirni znanstveni članek Ključne besede: 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
Objavljeno v RUP: 17.12.2020; Ogledov: 3972; Prenosov: 163
 Povezava na celotno besedilo |
8. Strong cliques in diamond-free graphsNina Chiarelli, Berenice Martínez-Barona, Martin Milanič, Jérôme Monnot, Peter Muršič, 2020, objavljeni znanstveni prispevek na konferenci Ključne besede: maximal clique, maximal stable set, diamond-free graph, strong clique, simplicial clique, CIS graph, NP-hard problem, linear-time algorithm, Erdős-Hajnal property
Objavljeno v RUP: 10.11.2020; Ogledov: 3373; Prenosov: 61
Povezava na celotno besedilo |
9. |
10. |
