1. Excluding an induced wheel minor in graphs without large induced starsMujin Choi, Claire Hilaire, Martin Milanič, Sebastian Wiederrecht, 2026, published scientific conference contribution Abstract: We study a conjecture due to Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht stating that for any positive integer d and any planar graph H, the class of all K_{1,d}-free graphs without H as an induced minor has bounded tree-independence number. A k-wheel is the graph obtained from a cycle of length k by adding a vertex adjacent to all vertices of the cycle. We show that the conjecture of Dallard et al. is true when H is a k-wheel for any k at least 3. Our proof uses a generalization of the concept of brambles to tree-independence number. As a consequence of our main result, several important NP-hard problems such as Maximum Independent Set are tractable on K_{1,d}-free graphs without large induced wheel minors. Moreover, for fixed d and k, we provide a polynomial-time algorithm that, given a K_{1,d}-free graph G as input, finds an induced minor model of a k-wheel in G if one exists.
Keywords: induced minor, wheel, tree-independence number, Maximum Independent Set
Published in RUP: 25.03.2026; Views: 434; Downloads: 2
 Link to file
This document has more files! More... |
2. Paint cost spectrum of perfect k-ary treesSonwabile Mafunda, Jonathan L. Merzel, Katherine E. Perry, Anna Varvak, 2026, original scientific article Abstract: We determine the paint cost spectrum for perfect k-ary trees. A coloring of the vertices of a graph G with d colors is said to be d-distinguishing if only the trivial automorphism preserves the color classes. The smallest such d is the distinguishing number of G and is denoted Dist(G). The paint cost of d-distinguishing G, denoted ρd(G), is the minimum size of the complement of a color class over all d-distinguishing colorings. A subset S of the vertices of G is said to be a fixing set for G if the only automorphsim that fixes the vertices in S pointwise is the trivial automorphism. The cardinality of a smallest fixing set is denoted Fix(G). In this paper, we explore the breaking of symmetry in perfect k-ary trees by investigating what we define as the paint cost spectrum of a graph G: (Dist(G); ρDist(G)(G), ρDist(G)+1(G), . . . , ρFix(G)+1(G)) and the paint cost ratio of G, which is defined to be the fraction of paint costs in the paint cost spectrum equal to Fix(G). We determine both the paint cost spectrum and the paint cost ratio completely for perfect k-ary trees. We also prove a lemma that is of interest in its own right: given an n-tuple, n ≥ 2 of distinct elements of an ordered abelian group and 1 ≤ k ≤ n! − 1, there exists a k × n row permuted matrix with distinct column sums.
Keywords: distinguishing coloring, fixing set, symmetry, cost of distinguishing
Published in RUP: 23.03.2026; Views: 366; Downloads: 7
 Full text (441,47 KB) |
3. Mobile mutual-visibility sets in graphsMagda Dettlaff, Magdalena Lemańska, Juan A. Rodríguez-Velázquez, Ismael G. Yero, 2026, original scientific article Abstract: Given a connected graph G, the mutual-visibility number of G is the cardinality of a largest set S such that for every pair of vertices x, y ∈ S there exists a shortest x, y-path whose interior vertices are not contained in S. Assume that a robot is assigned to each vertex of the set S. At each stage, one robot can move to a neighbouring vertex. Then S is a mobile mutual-visibility set of G if there exists a sequence of moves of the robots such that all the vertices of G are visited while maintaining the mutual-visibility property at all times. The mobile mutual-visibility number of G, denoted Mobµ(G), is the cardinality of a largest mobile mutual-visibility set of G. In this paper we introduce the concept of the mobile mutual-visibility number of a graph. We begin with some basic properties of the mobile mutual-visibility number of G and its relationship with the mutual-visibility number of G. We give exact values of Mobµ(G) for particular classes of graphs, i.e. cycles, wheels, complete bipartite graphs, and block graphs (in particular trees). Moreover, we present bounds for the lexicographic product of two graphs and show characterizations of the graphs achieving the limit values of some of these bounds. As a consequence of this study, we deduce that the decision problem concerning finding the mobile mutual-visibility number is NP-hard. Finally, we focus our attention on the mobile mutual-visibility number of line graphs of complete graphs, prism graphs and strong grids of two paths.
Keywords: mobile mutual-visibility set, mutual-visibility number, total mutual-visibility
Published in RUP: 03.03.2026; Views: 400; Downloads: 21
Full text (398,89 KB) |
4. |
5. |
6. Generalization of edge general position problemPaul Manuel, R. Prabha, Sandi Klavžar, 2025, original scientific article Abstract: 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.
Keywords: general position set, edge geodesic cover problem, edge k-general position problem, torus network, hypercube, Benes network
Published in RUP: 03.11.2025; Views: 583; Downloads: 4
Full text (812,56 KB) |
7. The independence polynomial of trees is not always log-concave starting from order 26Ohr Kadrawi, Vadim Levit, 2025, original scientific article Abstract: An independent set in a graph is a collection of vertices that are not adjacent to each other. The cardinality of the largest independent set in G is represented by α(G). The independence polynomial of a graph G = (V, E) was introduced by Gutman and Harary in 1983 and is defined as
I(G; x) = Σ_{k = 0}^α(G) s_k x^k = s₀ + s₁x + s₂x² + ... + s_α(G)x^α(G), where sk represents the number of independent sets in G of size k.
The problem raised by Alavi, Malde, Schwenk, and Erdös in 1987 stated that the independence polynomials of trees are unimodal, and many researchers believed that this problem could be strengthened up to its corresponding log-concave version. However, in 2023, this conjecture was shown to be false by Kadrawi, Levit, Yosef, and Mizrachi. In this paper, we provide further evidence against this conjecture by presenting infinite families of trees with independence polynomials that are not log-concave.
Keywords: tree, independent set, independence polynomial, unimodality, log-concavity
Published in RUP: 22.10.2025; Views: 1427; Downloads: 5
Full text (352,77 KB) |
8. Mutual-visibility problems in Kneser and Johnson graphsGülnaz Boruzanlı Ekinci, Csilla Bujtás, 2025, original scientific article Abstract: 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.
Keywords: mutual-visibility set, total mutual-visibility set, Kneser graph, bipartite Kneser graph, Johnson graph, Turán-type problem, covering design
Published in RUP: 22.10.2025; Views: 712; Downloads: 9
Full text (426,16 KB) |
9. Cubes of symmetric designsVedran Krčadinac, Mario Osvin Pavčević, Kristijan Tabak, 2025, original scientific article Abstract: We study n-dimensional matrices with {0, 1}-entries (n-cubes) such that all their 2-dimensional slices are incidence matrices of symmetric designs. A known construction of these objects obtained from difference sets is generalized so that the resulting n-cubes may have inequivalent slices. For suitable parameters, they can be transformed into n-dimensional Hadamard matrices with this property. In contrast, previously known constructions of n-dimensional designs all give examples with equivalent slices.
Keywords: symmetric design, difference set, Hadamard matrix
Published in RUP: 21.10.2025; Views: 474; Downloads: 2
Full text (121,51 KB) |
10. Perfect phylogenies via the minimum uncovering branching problem : efficiently solvable casesNarmina Baghirova, Esther Galby, Martin Milanič, 2025, original scientific article Abstract: In this paper, we present new efficiently solvable cases of the Minimum Uncovering Branching problem, an optimization problem with applications in cancer genomics introduced by Hujdurovi´c, Husi´c, Milaniˇc, Rizzi, and Tomescu in 2018. The problem involves a family of finite sets, and the goal is to map each non-maximal set to exactly one set that contains it, minimizing the sum of uncovered elements across all sets in the family. Hujdurovi´c et al. formulated the problem in terms of branchings of the digraph formed by the proper set inclusion relation on the input sets and studied the problem complexity based on properties of the corresponding partially ordered set, in particular, with respect to its height and width, defined respectively as the maximum cardinality of a chain and an antichain. They showed that the problem is APX-complete for instances of bounded height and that a constant-factor approximation algorithm exists for instances of bounded width, but left the exact complexity for bounded-width instances open. In this paper, we answer this question by proving that the problem is solvable in polynomial time. We derive this result by examining the structural properties of optimal solutions and reducing the problem to computing maximum matchings in bipartite graphs and maximum weight antichains in partially ordered sets. We also introduce a new polynomially computable lower bound and identify another condition for polynomial-time solvability.
Keywords: perfect phylogeny, branching, partially ordered set, antichain, width
Published in RUP: 13.10.2025; Views: 637; Downloads: 9
Full text (793,74 KB)
This document has more files! More... |
