51. On relationships between treewidth, clique number, tree-independence number, and induced minors : master’s thesisÐorđe Vasić, 2025, master's thesis Keywords: treewidth, clique number, tree-independence number, induced minor, hered itary graph class, bipartite chain graph
Published in RUP: 11.09.2025; Views: 602; Downloads: 7
 Full text (839,36 KB) |
52. The Gray graph is a unit-distance graphLeah Berman, Gábor Gévay, Tomaž Pisanski, 2025, original scientific article Abstract: In this note we give a construction proving that the Gray graph, which is the smallestcubic semisymmetric graph, is a unit-distance graph.
Keywords: polycirculant, unit-distance graph, Gray graph, ADAM graph, generalized Petersen graph
Published in RUP: 10.09.2025; Views: 514; Downloads: 2
Full text (951,83 KB) |
53. Tetravalent distance magic graphs of small order and an infinite family of examplesKsenija Rozman, Primož Šparl, 2025, original scientific article Abstract: A graph of order ▫$n$▫ is distance magic if it admits a bijective labeling of its vertices with integers from ▫$1$▫ to ▫$n$▫ such that each vertex has the same sum of the labels of its neighbors. This paper contributes to the long term project of characterizing all tetravalent distance magic graphs. With the help of a computer we find that out of almost nine million connected tetravalent graphs up to order 16 only nine are distance magic. In fact, besides the six well known wreath graphs there are only three other examples, one of each of the orders 12, 14 and 16. We introduce a generalization of wreath graphs, the so-called quasi wreath graphs, and classify all distance magic graphs among them. This way we obtain infinitely many new tetravalent distance magic graphs. Moreover, the two non-wreath graphs of orders 12 and 14 are quasi wreath graphs while the one of order 16 can be obtained from a quasi wreath graph of order 14 using a simple construction due to Kovář, Fronček and Kovářová.
Keywords: distance magic, tetravalent, quasi wreath graph
Published in RUP: 10.09.2025; Views: 364; Downloads: 5
Full text (457,53 KB) |
54. Coverings of general digraphsAleksander Malnič, Boris Zgrablić, 2025, original scientific article Abstract: A unified theory of covering projections of graphs and digraphs is presented as one theory by considering coverings of general digraphs, where multiple directed and undirected edges together with oriented and unoriented loops and semiedges, are allowed. It transpires that coverings of general digraphs can display certain pathological behaviour since the naturally defined projections of their underlying graphs may not be coverings in the usual topological sense. Consequently, homotopy does not always lift, although the unique walk lifting property still holds. Yet, it is still possible to grasp such coverings algebraically in terms of the action of the fundamental monoid. This action is permutational and has certain nice properties that monoid actions in general do not have. As a consequence, such projections can be studied combinatorially in terms of voltages. The problem of isomorphism and equivalence, and in particular, the problem of lifting automorphisms, is treated in depth. All known results about covering projections of graphs are simple corollaries of just three general theorems.
Keywords: mixed graph, general digraph, dart, covering projection, voltage, homotopy, monoid action, lifting automorphisms
Published in RUP: 10.09.2025; Views: 491; Downloads: 17
Full text (569,42 KB) |
55. On regular graphs with Šoltés verticesNino Bašić, Martin Knor, Riste Škrekovski, 2025, original scientific article Abstract: Let ▫$W(G)$▫ be the Wiener index of a graph ▫$G$▫. We say that a vertex ▫$v \in V(G)$▫ is a Šoltés vertex in ▫$G$▫ if ▫$W(G - v) = W(G)$▫, i.e. the Wiener index does not change if the vertex ▫$v$▫ is removed. In 1991, Šoltés posed the problem of identifying all connected graphs ▫$G$▫ with the property that all vertices of ▫$G$▫ are Šoltés vertices. The only such graph known to this day is ▫$C_{11}$▫. As the original problem appears to be too challenging, several relaxations were studied: one may look for graphs with at least ▫$k$▫ Šoltés vertices; or one may look for ▫$\alpha$▫-Šoltés graphs, i.e. graphs where the ratio between the number of Šoltés vertices and the order of the graph is at least ▫$\alpha$▫. Note that the original problem is, in fact, to find all ▫$1$▫-Šoltés graphs. We intuitively believe that every ▫$1$▫-Šoltés graph has to be regular and has to possess a high degree of symmetry. Therefore, we are interested in regular graphs that contain one or more Šoltés vertices. In this paper, we present several partial results. For every ▫$r\ge 1$▫ we describe a construction of an infinite family of cubic ▫$2$▫-connected graphs with at least ▫$2^r$▫ Šoltés vertices. Moreover, we report that a computer search on publicly available collections of vertex-transitive graphs did not reveal any ▫$1$▫-Šoltés graph. We are only able to provide examples of large ▫$\frac{1}{3}$▫-Šoltés graphs that are obtained by truncating certain cubic vertex-transitive graphs. This leads us to believe that no ▫$1$▫-Šoltés graph other than ▫$C_{11}$▫ exists.
Keywords: Šoltés problem, Wiener index, regular graphs, cubic graphs, Cayley graph, Šoltés vertex
Published in RUP: 10.09.2025; Views: 384; Downloads: 2
Full text (456,75 KB) |
56. Homomorphisms from the Coxeter graphMarko Orel, Draženka Višnjić, 2025, original scientific article Abstract: Let $S_n(\mathbb{F}_2)$ be the set of all $n\times n$ symmetric matrices with coefficients in the binary field $\mathbb{F}_2=\{0,1\}$, and let $SGL_n(\mathbb{F}_2)$ be its subset formed by invertible matrices. Let $\widehat{\Gamma}_n$ be the graph with the vertex set $S_n(\mathbb{F}_2)$ where a pair of vertices $\{A,B\}$ form an edge if and only if $rank(A-B)=1$. Similarly, let $\Gamma_n$ be the subgraph in $\widehat{\Gamma}_n$, which is induced by the set $SGL_n(\mathbb{F}_2)$. Graph $\Gamma_n$ generalizes the well-known Coxeter graph, which is isomorphic to $\Gamma_3$. Motivated by research topics in coding theory, matrix theory, and graph theory, this paper represents the first step towards the characterization of all graph homomorphisms $\Phi: \Gamma_n\to \widehat{\Gamma}_m$ where $n,m$ are positive integers. Here, the case $n=3$ is solved.
Keywords: preserver problems, symmetric matrices, invertible matrices, binary field, rank, graph homomorphisms, Coxeter graph
Published in RUP: 27.08.2025; Views: 475; Downloads: 5
Full text (1,42 MB)
This document has more files! More... |
57. On the proper interval completion problem within some chordal subclassesFrançois Dross, Claire Hilaire, Ivo Koch, Valeria Alejandra Leoni, Nina Pardal, María Inés Lopez Pujato, Vinicius Fernandes dos Santos, 2025, original scientific article Abstract: Given a property (graph class) Π, a graph G, and an integer k, the Π-completion problem consists of deciding whether we can turn G into a graph with the property Π by adding at most k edges to G. The Π-completion problem is known to be NP-hard for general graphs when Π is the property of being a proper interval graph (PIG). In this work, we study the PIG-completion problem within different subclasses of chordal graphs. We show that the problem remains NP-complete even when restricted to split graphs. We then turn our attention to positive results and present polynomial time algorithms to solve the PIG-completion problem when the input is restricted to caterpillar and threshold graphs. We also present an efficient algorithm for the minimum co-bipartite-completion for quasi-threshold graphs, which provides a lower bound for the PIG-completion problem within this graph class.
Keywords: proper interval completion, split graph, threshold graph, quasi-threshold graph, caterpillar
Published in RUP: 06.08.2025; Views: 429; Downloads: 9
Full text (824,75 KB)
This document has more files! More... |
58. On balanceable and simply balanceable regular graphsMilad Ahanjideh, Martin Milanič, Mary Agnes Milanič, 2025, original scientific article Abstract: We continue the study of balanceable graphs, defined by Caro, Hansberg, and Montejano in 2021 as graphs G such that any 2-coloring of the edges of a sufficiently large complete graph containing sufficiently many edges of each color contains a balanced copy of G (that is, a copy with half the edges of each color). While the problem of recognizing balanceable graphs was conjectured to be NP-complete by Dailly, Hansberg, and Ventura in 2021, balanceable graphs admit an elegant combinatorial characterization: a graph is balanceable if and only there exist two vertex subsets, one containing half of all the graph’s edges and another one such that the corresponding cut contains half of all the graph’s edges. We consider a special case of this property, namely when one of the two sets is a vertex cover, and call the corresponding graphs simply balanceable. We prove a number of results on balanceable and simply balanceable regular graphs. First, we characterize simply balanceable regular graphs via a condition involving the independence number of the graph. Second, we address a question of Dailly, Hansberg, and Ventura from 2021 and show that every cubic graph is balanceable. Third, using Brooks’ theorem, we show that every 4-regular graph with order divisible by 4 is balanceable. Finally, we show that it is NP-complete to determine if a 9-regular graph is simply balanceable.
Keywords: balanceable graph, simply balanceable graph, cubic graph, 4-regular graph, regular graph, independent set
Published in RUP: 06.08.2025; Views: 531; Downloads: 7
Full text (530,38 KB)
This document has more files! More... |
59. On 3-isoregularity of multicirculantsKlavdija Kutnar, Dragan Marušič, Štefko Miklavič, 2025, original scientific article Abstract: A graph is said to be k-isoregular if any two vertex subsets of cardinality at most k, that induce subgraphs of the same isomorphism type, have the same number of neighbors. It is shown that no 3-isoregular bicirculant (and more generally, no locally 3-isoregular bicirculant) of order twice an odd number exists. Further, partial results for bicirculants of order twice an even number as well as tricirculants of specific orders, are also obtained. Since 3-isoregular graphs are necessarily strongly regular, a motivation for the above result about bicirculants is that it brings us a step closer to obtaining a direct proof of a classical consequence of the Classification of Finite Simple Groups, that no simply primitive group of degree twice a prime exists for primes greater than 5.
Keywords: 3-isoregularity, strongly regular graph, bicirculant, tricirculant
Published in RUP: 06.08.2025; Views: 410; Downloads: 3
Full text (233,35 KB) |
60. |
