1. Optimizacija in grafi : učinkovitost nekaterih algoritmov v teoriji in praksiMarko Grgurovič, 2025, doktorska disertacija 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: 222; Prenosov: 5
 Celotno besedilo (927,66 KB)
Gradivo ima več datotek! Več... |
2. On bipartite (1,1,k)-mixed graphsCristina Dalfó, Grahame Erskine, Geoffrey Exoo, Miquel Àngel Fiol, James Tuite, 2025, izvirni znanstveni članek Opis: Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are bipartite and in which the undirected and directed degrees are one. The best graphs, in terms of the number of vertices, are presented for small diameters. Moreover, two infinite families of such graphs with diameter k and number of vertices of the order of 2k/2 are proposed, one of them being totally regular (1,1)-mixed graphs. In addition, we present two more infinite families called chordal ring and chordal double ring mixed graphs, which are bipartite and related to tessellations of the plane. Finally, we give an upper bound that improves the Moore bound for bipartite mixed graphs for r = z = 1.
Ključne besede: mixed graph, degree/diameter problem, Moore bound, bipartite graph
Objavljeno v RUP: 03.11.2025; Ogledov: 419; Prenosov: 0
Celotno besedilo (628,98 KB) |
3. On extremal (almost) edge-girth-regular graphsGabriela Araujo-Pardo, György Kiss, István Porupsánszki, 2025, izvirni znanstveni članek 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: 322; Prenosov: 2
Celotno besedilo (547,76 KB) |
4. |
5. Totally regular mixed graphs constructed from the CD(n,q) graphs of Lazebnik, Ustimenko and WoldarTatiana Jajcayova, Robert Jajcay, 2025, izvirni znanstveni članek 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: 268; Prenosov: 2
Celotno besedilo (574,95 KB) |
6. |
7. The extremal generalised Randić index for a given degree rangeJohn Haslegrave, 2025, izvirni znanstveni članek 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: 284; Prenosov: 1
Celotno besedilo (403,78 KB) |
8. Generalization of edge general position problemPaul Manuel, R. Prabha, Sandi Klavžar, 2025, izvirni znanstveni članek Opis: The edge geodesic cover problem of a graph G is to find a smallest number of geodesics that cover the edge set of G. The edge k-general position problem is introduced as the problem to find a largest set S of edges of G such that at most k-1 edges of S lie on a common geodesic. We show that these are dual min-max problems and connect them to an edge geodesic partition problem. Using these connections, exact values of the edge k-general position number is determined for different values of k and for various networks including torus networks, hypercubes, and Benes networks.
Ključne besede: general position set, edge geodesic cover problem, edge k-general position problem, torus network, hypercube, Benes network
Objavljeno v RUP: 03.11.2025; Ogledov: 256; Prenosov: 1
Celotno besedilo (812,56 KB) |
9. On edge-girth-regular graphs: lower bounds and new familiesIstván Porupsánszki, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: cage problem, extremal graph theory, generalized polygons, ovoids
Objavljeno v RUP: 22.10.2025; Ogledov: 352; Prenosov: 1
Celotno besedilo (358,49 KB) |
10. Mutual-visibility problems in Kneser and Johnson graphsGülnaz Boruzanlı Ekinci, Csilla Bujtás, 2025, izvirni znanstveni članek Opis: Let G be a connected graph and X ⊆ V(G). By definition, two vertices u and v are X-visible in G if there exists a shortest u, v-path with all internal vertices being outside of the set X. The largest size of X such that any two vertices of G (resp. any two vertices from X) are X-visible is the total mutual-visibility number (resp. the mutual-visibility number) of G.
In this paper, we determine the total mutual-visibility number of Kneser graphs, bipartite Kneser graphs, and Johnson graphs. The formulas proved for Kneser, and bipartite Kneser graphs are related to the size of transversal-critical uniform hypergraphs, while the total mutual-visibility number of Johnson graphs is equal to a hypergraph Turán number. Exact values or estimations for the mutual-visibility number over these graph classes are also established.
Ključne besede: mutual-visibility set, total mutual-visibility set, Kneser graph, bipartite Kneser graph, Johnson graph, Turán-type problem, covering design
Objavljeno v RUP: 22.10.2025; Ogledov: 313; Prenosov: 6
Celotno besedilo (426,16 KB) |
