Results 1 to 10 of about 2,369,458 (297)
Solving Robust Variants of the Maximum Weighted Independent Set Problem on Trees [PDF]
Mathematics, 2020 This paper deals with the maximum weighted independent set (MWIS) problem. We consider several robust variants of the MWIS problem on trees and prove that most of them are NP-hard.
Ana Klobučar, Robert Manger
doaj +2 more sources
Number of maximal 2-component independent sets in forests
AIMS Mathematics, 2022 Let $ G = (V(G), E(G)) $ be a graph. For a positive integer $ k $, we call $ S\subseteq V(G) $ a $ k $-component independent set of $ G $ if each component of $ G[S] $ has order at most $ k $.
Shuting Cheng, Baoyindureng Wu
doaj +1 more source
Independent partial domination
Cubo, 2021 For $p\in(0,1]$, a set $S\subseteq V$ is said to $p$-dominate or partially dominate a graph $G = (V, E)$ if $\frac{|N[S]|}{|V|}\geq p$. The minimum cardinality among all $p$-dominating sets is called the $p$-domination number and it is denoted by ...
L. Philo Nithya +1 more
doaj +1 more source
Minimization of Boolean functions in the class of orthogonal disjunctive normal forms
Informatika, 2021 The orthogonal disjunctive normal forms (DNFs) of Boolean functions have wide applications in the logical design of discrete devices. The problem of DNF orthogonalization is to get for a given function such a DNF that any two its terms would be ...
Yu. V. Pottosin
doaj +1 more source
On the Outer-Independent Double Roman Domination of Graphs
Frontiers in Applied Mathematics and Statistics, 2021 An outer-independent double Roman dominating function (OIDRDF) of a graph G is a function h:V(G)→{0,1,2,3} such that i) every vertex v with f(v)=0 is adjacent to at least one vertex with label 3 or to at least two vertices with label 2, ii) every vertex ...
Yongsheng Rao +4 more
doaj +1 more source
The hardness of the independence and matching clutter of a graph [PDF]
Opuscula Mathematica, 2016 A clutter (or antichain or Sperner family) \(L\) is a pair \((V,E)\), where \(V\) is a finite set and \(E\) is a family of subsets of \(V\) none of which is a subset of another.
Sasun Hambardzumyan +3 more
doaj +1 more source
Independent Dominating Set on Chain of Fuzzy Graphs
Tikrit Journal of Pure Science, 2023 In this paper, we applied some properties on chain fuzzy graphs, which comprise vertex identification. These properties are independent sets and independent dominant sets.
Russel H. Majeed, Nabeel E. Arif
doaj +1 more source
Edge Metric Dimension and Edge Basis of One-Heptagonal Carbon Nanocone Networks
IEEE Access, 2022 A molecular (chemical) graph is a simple connected graph, where the vertices represent the compound’s atoms and the edges represent bonds between the atoms, and the degree (valence) of every vertex (atom) is not more than four.
Karnika Sharma +2 more
doaj +1 more source
Eternal Independent Sets in Graphs
Theory and Applications of Graphs, 2016 The use of mobile guards to protect a graph has received much attention in the literature of late in the form of eternal dominating sets, eternal vertex covers and other models of graph protection.
Yair Caro, William Klostermeyer
doaj +1 more source
On the Independence Number of Cayley Digraphs of Clifford Semigroups
Mathematics, 2023 Let S be a Clifford semigroup and A a subset of S. We write Cay(S,A) for the Cayley digraph of a Clifford semigroup S relative to A. The (weak, path, weak path) independence number of a graph is the maximum cardinality of an (weakly, path, weakly path ...
Krittawit Limkul, Sayan Panma
doaj +1 more source