Search the repository

Abstract: Label the vertices of the complete graph K_v with the integers {0, 1, …, v − 1} and define the length l of the edge between distinct vertices labeled x and y by ℓ(x, y) = min (|y − x|,v − |y − x|). A realization of a multiset L of size v − 1 is a Hamiltonian path through K_v whose edge labels are L. The Buratti-Horak-Rosa (BHR) Conjecture is that there is a realization for a multiset L if and only if for any divisor d of v the number of multiples of d in L is at most v − d. We introduce “grid-based graphs" as a useful tool for constructing particular types of realizations, called “linear realizations,"especially when the multiset in question has a support of size 3. This lets us prove many new instances of the BHR Conjecture, including those for multisets of the form {1^a, x^b, y^c} when a ≥ x + y − ϵ, where ϵ is the number of even elements in {x, y}, and those for all multisets of the following forms for sufficiently large v with gcd (v,y) = 1 for all y ∈ L: •{1^a, 2^b, x^c}, except possibly when a ∈ {1, 2} and x is odd, •{1^a, x^b, (x + 1)^c}. This establishes that there are infinitely many sets U of size 3 for which there are infinitely many values of v where the BHR Conjecture holds for each multiset with support U. We also show that the BHR Conjecture holds for {1^a, x^b, (x + 1)^c} when x ∈ {7, 9, 10} and gcd (v, x) = gcd (v, x + 1) = 1.
Keywords: complete graph, Hamiltonian path, edge-length, realization, grid-based graph
Published in RUP: 28.09.2026; Views: 285; Downloads: 3
Full text (509,79 KB)

Abstract: The subdivided double construction on 4-regular graphs was used by Potočnik and Wilson to explore semi-symmetric graphs. It preserves the property of being semi-symmetric, and can be used to construct every semi-symmetric 4-regular graph that contains a pair of twin vertices. We show that (regardless of symmetry) subdivided doubles have another curious property: each of their many Hamiltonian cycles is complementary to another Hamiltonian cycle.
Keywords: Hamiltonian cycle, Hamiltonian decomposition, subdivided double, tetravalent graph
Published in RUP: 28.09.2026; Views: 241; Downloads: 1
Full text (490,03 KB)

Abstract: Consider the class of finite graphs G such that G does not have the fixed clique property and every proper simplicial retract has the fixed clique property. Within this class, we characterize the graphs such that every simplicial automorphism has a vertex that is adjacent or equal to its image, and such that the complement of G has maximum degree 3 and a vertex of degree 2. It turns out that this property is close to an NP-complete problem with a rather beautiful embedding of 3SAT into combinatorics.
Keywords: fixed clique property, retraction, octahedral graph, complexity
Published in RUP: 23.09.2026; Views: 268; Downloads: 9
Full text (491,83 KB)

Abstract: The scramble number of a graph is an invariant recently developed to study chip-firing games and divisorial gonality. In this paper we introduce the screewidth of a graph, based on a variation of the existing literature on tree-cut decompositions. We prove that this invariant serves as an upper bound on scramble number, though they are not always equal. We study properties of screewidth, and present results and conjectures on its connection to divisorial gonality.
Keywords: graph theory, tree-cut decomposition, scramble number, gonality
Published in RUP: 16.09.2026; Views: 274; Downloads: 3
Full text (904,42 KB)

Abstract: Graph burning is a round-based game or process that discretely models the spread of influence throughout a network. We introduce a generalization of graph burning which applies to hypergraphs, as well as a variant called "lazy" hypergraph burning. Interestingly, lazily burning a graph is trivial, while lazily burning a hypergraph can be quite complicated. Moreover, the lazy burning model is a useful tool for analyzing the round-based model. One of our key results is that arbitrary hypergraphs do not satisfy a bound analogous to the one in the Burning Number Conjecture for graphs. We also obtain bounds on the burning number and lazy burning number of a hypergraph in terms of its parameters, and present several open problems in the field of (lazy) hypergraph burning.
Keywords: Combinatorial games on graphs, pursuit-evasion, graph searching, graph burning, hypergraph theory
Published in RUP: 18.08.2026; Views: 506; Downloads: 13
Full text (413,95 KB)