Iskanje po repozitoriju

Opis: The uniform Hamilton-Waterloo Problem (HWP) asks for a resolvable (CM, CN)-decomposition of Kv into α CM-factors and β CN-factors. We denote a solution to the uniform Hamilton-Waterloo problem by HWP(v; M, N; α, β). Our research concentrates on addressing some of the remaining unresolved cases, which pose a significant challenge to generalize. We place a particular emphasis on instances where the gcd (M, N) = {2, 3}, with a specific focus on the parameter M = 6. We introduce modifications to some known structures, and develop new approaches to resolving these outstanding challenges in the construction of uniform 2-factorizations. This innovative method not only extends the scope of solved cases, but also contributes to a deeper understanding of the complexity involved in solving the Hamilton-Waterloo Problem.
Ključne besede: 2-factorizations, Hamilton-Waterloo problem, Oberwolfach problem, cycle decomposition, resolvable decompositions
Objavljeno v RUP: 11.08.2026; Ogledov: 265; Prenosov: 3
Celotno besedilo (526,92 KB)

Ključne besede: dynamic programming, combinatorial optimization, ant colony optimization, shortest path problem, bottleneck path problem, traveling salesman problem, parallel algorithms, asymptotic analysis, expected-case analysis
Objavljeno v RUP: 17.12.2025; Ogledov: 1355; Prenosov: 18
Celotno besedilo (927,66 KB)
Gradivo ima več datotek! Več...

Opis: 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.
Ključne besede: edge-girth-regular graph, cage problem, finite biaffine planes
Objavljeno v RUP: 03.11.2025; Ogledov: 1055; Prenosov: 8
Celotno besedilo (547,76 KB)

Opis: The CD(n,q) graphs are connected components of q-regular graphs D(n,q) introduced in 1995 by Lazebnik and Ustimenko. They constitute the best universal family of regular graphs of prime power degree with regard to the Cage Problem which calls for determining the orders of the smallest k-regular graphs of girth g. The girths of the CD(n,q) graphs are known to be at least n+4 in case of even n, and n+5 for odd n. We propose to extend the use of the CD(n,q) graphs into the area of mixed graphs by adding directions to certain edges of the C(n,q)graphs. In the context of mixed graphs, graphs in which the number of incident non-oriented edges is the same for all vertices, and the numbers of out-going and in-going edges are also equal and the same for all vertices, are of special interest and are called totally regular mixed graphs. In view of the special properties of the original C(n,q) graphs with regard to cages, we believe that the totally regular mixed graphs we propose to study may also prove to be extremal with regard to properties sought for in the area of mixed graphs.
Ključne besede: cage problem, girth, degree, mixed graphs
Objavljeno v RUP: 03.11.2025; Ogledov: 1159; Prenosov: 11
Celotno besedilo (574,95 KB)

Opis: 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.
Ključne besede: Randić index, bounded-degree graph, extremal problem
Objavljeno v RUP: 03.11.2025; Ogledov: 857; Prenosov: 8
Celotno besedilo (403,78 KB)