Dominating sets for split and bipartite graphs
From MaRDI portal
Publication:794174
DOI10.1016/0020-0190(84)90126-1zbMath0539.68058OpenAlexW1984394682WikidataQ29041830 ScholiaQ29041830MaRDI QIDQ794174
Publication date: 1984
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(84)90126-1
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Satgraphs and independent domination. I ⋮ Independent domination in hereditary classes ⋮ Decremental Optimization of Dominating Sets Under the Reconfiguration Framework ⋮ Computing role assignments of split graphs ⋮ The neighborhood polynomial of chordal graphs ⋮ \((1, j)\)-set problem in graphs ⋮ Domination in some subclasses of bipartite graphs ⋮ The Complexity of Dominating Set Reconfiguration ⋮ And/or-convexity: a graph convexity based on processes and deadlock models ⋮ Well-partitioned chordal graphs ⋮ Right angle free subsets in the plane ⋮ Some advances on the set covering polyhedron of circulant matrices ⋮ One-node cutsets and the dominating set polytope ⋮ A complexity dichotomy and a new boundary class for the dominating set problem ⋮ Vertex-Neighbor-Scattering Number of Bipartite Graphs ⋮ Graphs with maximal induced matchings of the same size ⋮ Algorithmic Aspects of Disjunctive Domination in Graphs ⋮ On some domination colorings of graphs ⋮ Monopolar graphs: complexity of computing classical graph parameters ⋮ On dominating set polyhedra of circular interval graphs ⋮ Algorithmic aspects of the generalized clique-transversal problem on chordal graphs ⋮ Broadcast domination and multipacking in strongly chordal graphs ⋮ The Neighborhood Polynomial of Chordal Graphs ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Parameterized complexity of multicut in weighted trees ⋮ Unnamed Item ⋮ Broadcasting in split graphs ⋮ Colouring a dominating set without conflicts: \(q\)-subset square colouring ⋮ Unique response Roman domination: complexity and algorithms ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ A decidability result for the dominating set problem ⋮ Edge deletion to tree-like graph classes ⋮ Complexity results on cosecure domination in graphs ⋮ Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs ⋮ On graphs for which the connected domination number is at most the total domination number ⋮ Cosecure domination: hardness results and algorithms ⋮ Some new algorithmic results on co-secure domination in graphs ⋮ Domination and its variants in split graphs \(-\text{P}\) versus NPC dichotomy ⋮ Algorithm complexity of neighborhood total domination and \((\rho,\gamma_{\mathrm{nt}})\)-graphs ⋮ The weighted perfect domination problem ⋮ The complexity of secure domination problem in graphs ⋮ On dominating sets whose induced subgraphs have a bounded diameter ⋮ Computing a minimum outer-connected dominating set for the class of chordal graphs ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ On the geodetic number of complementary prisms ⋮ Reducing the domination number of graphs via edge contractions and vertex deletions ⋮ The numerical invariants concerning the total domination for generalized Petersen graphs ⋮ Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs ⋮ Dominating sets in perfect graphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Independent dominating set problem revisited ⋮ Well-indumatched Trees and Graphs of Bounded Girth ⋮ A ZONAL ALGORITHM FOR CLUSTERING AN HOC NETWORKS ⋮ Variations of \(Y\)-dominating functions on graphs ⋮ Dominating cliques in graphs ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size ⋮ Restricted optimal pebbling and domination in graphs ⋮ The complexity of dominating set reconfiguration ⋮ Total domination in interval graphs ⋮ The algorithmic complexity of mixed domination in graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Dominating cliques in graphs ⋮ Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Unnamed Item ⋮ Algorithmic aspects of \(b\)-disjunctive domination in graphs ⋮ The complexity of the defensive domination problem in special graph classes ⋮ Vertex deletion problems on chordal graphs ⋮ Secure total domination in graphs: bounds and complexity ⋮ Vector domination in split-indifference graphs ⋮ Dominating sets reconfiguration under token sliding ⋮ Layered graphs: applications and algorithms ⋮ Algorithmic complexity of secure connected domination in graphs ⋮ Algorithmic aspects of secure connected domination in graphs ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ On the Convexity of Paths of Length Two in Undirected Graphs ⋮ Bounds on the bend number of split and cocomparability graphs ⋮ Domination problems on P5-free graphs ⋮ Algorithmic aspects of k-part degree restricted domination in graphs ⋮ Coloring a dominating set without conflicts: \(q\)-subset square coloring ⋮ The geodetic number of a graph ⋮ On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs ⋮ Approximation algorithms for clique transversals on some graph classes ⋮ On secure domination in graphs ⋮ Vertex Deletion Problems on Chordal Graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On domination and independent domination numbers of a graph
- Dominating sets and domatic number of circular arc graphs
- Contributions to the theory of domination, independence and irredundance in graphs
- A linear algorithm for the domination number of a tree
- Disjoint independent dominating sets in graphs
- Optimum domination in weighted trees
- Graph-theoretic parameters concerning domination, independence, and irredundance
- Total domination in graphs
- Dominating Sets in Chordal Graphs
- R -Domination in Graphs
- Towards a theory of domination in graphs
