Iskanje po repozitoriju

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: 455; Prenosov: 2
Povezava na datoteko
Gradivo ima več datotek! Več...

Opis: A dominating set S ⊆ V is a co-secure dominating set if for each u ∈ S there exists v ∈ V \ S such that v is adjacent to u and (S \ {u}) ∪ {v} is a dominating set. The cardinality of a minimum co-secure dominating set in G is called the cosecure domination number of G and is denoted by γcs(G). The study of a co-secure dominating set is important in interconnection networks as it studies its security. In cosecure domination, a guard can ensure the safety of only one of its adjacent unguarded vertices. This motivated us to define a new domination parameter called complete co-secure domination, in which a guard can move to any one of its adjacent unguarded vertices without compromising the protection of G. A co-secure dominating set S is called a complete co-secure dominating set if for every u ∈ S and for every v ∈ V \ S that is adjacent to u, (S \ {u})∪ {v} is a dominating set. The cardinality of a minimum complete co-secure dominating set is called the complete co-secure domination number of G and is denoted by γccs(G). In this paper, we study the complete co-secure domination in graphs and determined the lower and upper bounds and have checked their sharpness. We have proved that for any positive integer m, there exists a graph whose co-secure domination number is m and complete co-secure domination number is b, where m ≤ b ≤ 2m. We characterize graphs G such that γcs(G) = γccs(G). We obtain a condition for which γcs(G) = γccs(G) = γs(G) for graphs with δ(G) ≥ 2, thus partially resolving a question posed in paper from Arumugam, Ebadi and Manrique from 2014. We also obtain the complete co-secure domination number of some families of graphs.
Ključne besede: domination number, co-secure domination number, complete co-secure domination number
Objavljeno v RUP: 20.03.2026; Ogledov: 331; Prenosov: 14
Celotno besedilo (437,20 KB)

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: 416; Prenosov: 21
Celotno besedilo (398,89 KB)

Opis: A fullerene is an all-carbon molecule with a polyhedral structure where each atom is bonded to three other atoms and each face is either a pentagon or a hexagon. Fullerenes correspond to 3-regular planar graphs whose faces have sizes 5 or 6. The p-anionic Clar number C_(p)(G) of a fullerene G is equal to p + h, where h is maximized over all choices of p + h independent faces (exactly p pentagons and h hexagons) the deletion of whose vertices leave a graph with a perfect matching. This definition is motivated by the chemical observation that pentagonal rings can accommodate an extra electron, so that the pentagons of a fullerene with charge −p, compete with the hexagons to host ‘Clar sextets’ of six electrons, and pentagons will preferentially acquire the p excess electrons of the anion. Tight upper bounds are established for the p-anionic Clar number of fullerenes for p > 0. The upper bounds are derived via graph theoretic arguments and new results on minimal cyclic-k-edge cutsets in IPR fullerenes (fullerenes that have all pentagons pairwise disjoint). These bounds are shown to be tight by infinite families of fullerenes that achieve them.
Ključne besede: chemical graph theory, anionic Clar number, fullerenes
Objavljeno v RUP: 21.12.2025; Ogledov: 673; Prenosov: 1
Celotno besedilo (1,11 MB)

Opis: The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several NP-hard graph problems, like maximum-weight independent set, can be solved in time n^O(k) if the input n-vertex graph is given together with a tree decomposition of independence number k. Yolov, in SODA 2018, gave an algorithm that, given an n-vertex graph G and an integer k, in time n^O(k^3) either constructs a tree decomposition of G whose independence number is O(k^3) or correctly reports that the tree-independence number of G is larger than k. In this article, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. Our second result is that the exact computation of the tree-independence number is para-NP-hard: We show that for every constant k ≥ 4 it is NP-complete to decide whether a given graph has the tree-independence number at most k.
Ključne besede: tree-independence number, approximation, parameterized algorithm
Objavljeno v RUP: 16.12.2025; Ogledov: 678; Prenosov: 5
Celotno besedilo (1,45 MB)
Gradivo ima več datotek! Več...