1. Excluding an induced wheel minor in graphs without large induced starsMujin Choi, Claire Hilaire, Martin Milanič, Sebastian Wiederrecht, 2026, objavljeni znanstveni prispevek na konferenci Opis: 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.
Ključne besede: induced minor, wheel, tree-independence number, Maximum Independent Set
Objavljeno v RUP: 25.03.2026; Ogledov: 208; Prenosov: 2
 Povezava na datoteko
Gradivo ima več datotek! Več... |
2. Paint cost spectrum of perfect k-ary treesSonwabile Mafunda, Jonathan L. Merzel, Katherine E. Perry, Anna Varvak, 2026, izvirni znanstveni članek Opis: 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.
Ključne besede: distinguishing coloring, fixing set, symmetry, cost of distinguishing
Objavljeno v RUP: 23.03.2026; Ogledov: 166; Prenosov: 5
 Celotno besedilo (441,47 KB) |
3. Mobile mutual-visibility sets in graphsMagda Dettlaff, Magdalena Lemańska, Juan A. Rodríguez-Velázquez, Ismael G. Yero, 2026, izvirni znanstveni članek Opis: 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.
Ključne besede: mobile mutual-visibility set, mutual-visibility number, total mutual-visibility
Objavljeno v RUP: 03.03.2026; Ogledov: 242; Prenosov: 15
Celotno besedilo (398,89 KB) |
4. |
5. |
6. 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: 436; Prenosov: 3
Celotno besedilo (812,56 KB) |
7. The independence polynomial of trees is not always log-concave starting from order 26Ohr Kadrawi, Vadim Levit, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: tree, independent set, independence polynomial, unimodality, log-concavity
Objavljeno v RUP: 22.10.2025; Ogledov: 872; Prenosov: 2
Celotno besedilo (352,77 KB) |
8. 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: 503; Prenosov: 7
Celotno besedilo (426,16 KB) |
9. Cubes of symmetric designsVedran Krčadinac, Mario Osvin Pavčević, Kristijan Tabak, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: symmetric design, difference set, Hadamard matrix
Objavljeno v RUP: 21.10.2025; Ogledov: 382; Prenosov: 1
Celotno besedilo (121,51 KB) |
10. Perfect phylogenies via the minimum uncovering branching problem : efficiently solvable casesNarmina Baghirova, Esther Galby, Martin Milanič, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: perfect phylogeny, branching, partially ordered set, antichain, width
Objavljeno v RUP: 13.10.2025; Ogledov: 456; Prenosov: 6
Celotno besedilo (793,74 KB)
Gradivo ima več datotek! Več... |
