\(k\)-domination and \(k\)-independence in graphs: A survey

DOI10.1007/s00373-011-1040-3zbMath1234.05174OpenAlexW2017926358MaRDI QIDQ659765

Odile Favaron, Adriana Hansberg, Mustapha Chellali, Lutz Volkmann

Publication date: 24 January 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-011-1040-3

zbMATH Keywords

connected \(k\)-domination \(k\)-independence \(k\)-tuple domination \(k\)-domination \(k\)-irredundance \(k\)-star-forming \(l\)-total \(k\)-domination

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (82)

Domination, independent domination and \(k\)-independence in trees ⋮ A note on the annihilation number and 2-domination number of a tree ⋮ Balanced independent and dominating sets on colored interval graphs ⋮ The difference between the metric dimension and the determining number of a graph ⋮ On approximating (connected) 2-edge dominating set by a tree ⋮ A Taxonomy of Perfect Domination ⋮ On the complexity of reinforcement in graphs ⋮ Making a dominating set of a graph connected ⋮ Decreasing the maximum degree of a graph ⋮ The p-domination number of complete multipartite graphs ⋮ Algorithmic and structural aspects of the \(P_3\)-Radon number ⋮ Conjecture of TxGraffiti: Independence, domination, and matchings ⋮ The annihilation number does not bound the 2-domination number from the above ⋮ Isolation of cycles ⋮ Independent Roman domination and 2-independence in trees ⋮ Heuristics for \(k\)-domination models of facility location problems in street networks ⋮ Isolation of \(k\)-cliques ⋮ Graphs with \(\alpha _1\) and \(\tau _1\) both large ⋮ Covers and partial transversals of Latin squares ⋮ Relating the annihilation number and the 2-domination number of a tree ⋮ On the \(k\)-residue of disjoint unions of graphs with applications to \(k\)-independence ⋮ Roman domination and 2-independence in trees ⋮ On vertex independence number of uniform hypergraphs ⋮ \( P_5\)-isolation in graphs ⋮ On the signed (total) \(k\)-independence number in graphs ⋮ Trees with maximum \(p\)-reinforcement number ⋮ (Open) packing number of some graph products ⋮ \(K_{1, 2}\)-isolation number of claw-free cubic graphs ⋮ \(k\)-domination and total \(k\)-domination numbers in catacondensed hexagonal systems ⋮ Perfect Italian domination on planar and regular graphs ⋮ Nordhaus-Gaddum-type results on the connected edge domination number ⋮ Thresholds for the monochromatic clique transversal game ⋮ An upper bound on the \(P_3\)-Radon number ⋮ On bondage numbers of graphs: a survey with some comments ⋮ Unnamed Item ⋮ Client-server and cost effective sets in graphs ⋮ Domination number, independent domination number and 2-independence number in trees ⋮ On upper bounds for multiple domination numbers of graphs ⋮ Unnamed Item ⋮ On \(k\)-domination and \(j\)-independence in graphs ⋮ Algorithmic aspects of the \(k\)-domination problem in graphs ⋮ Partitions of graphs into small and large sets ⋮ Upper bounds on the \(k\)-forcing number of a graph ⋮ \([1,k\)-domination number of lexicographic products of graphs] ⋮ \( K_{1 , 2}\)-isolation in graphs ⋮ NP-hardness of multiple bondage in graphs ⋮ Relating the annihilation number and the 2-domination number of block graphs ⋮ Bounds on the 2-domination number ⋮ Constructing dominating sets in circulant graphs ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ A new generalization of kernels in digraphs ⋮ Grundy dominating sequences and zero forcing sets ⋮ Partial domination - the isolation number of a graph ⋮ Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture ⋮ On the 2-independence subdivision number of graphs ⋮ On the \(p\)-reinforcement and the complexity ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Complexity of \(k\)-rainbow independent domination and some results on the lexicographic product of graphs ⋮ Mixed Roman domination and 2-independence in trees ⋮ The <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>-independence number of graph products ⋮ 2-edge connected dominating sets and 2-connected dominating sets of a graph ⋮ On (1,2)-domination in cubic graphs ⋮ Bounds on weak Roman and 2-rainbow domination numbers ⋮ On the packing numbers in graphs ⋮ Zero forcing in claw-free cubic graphs ⋮ Multiple Domination ⋮ Bipartite graphs with close domination and \(k\)-domination numbers ⋮ ANOTHER LOOK AT k-DOMINATION IN GRAPHS ⋮ Admissible property of graphs in terms of radius ⋮ MAX for \(k\)-independence in multigraphs ⋮ Independent \((k + 1)\)-domination in \(k\)-trees ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ On the \(k\)-domination number of digraphs ⋮ Perfect domination ratios of Archimedean lattices ⋮ On the complexity of multiple bondage in graphs ⋮ On the signed 2-independence number of graphs ⋮ Edge domination and 2-independence in trees ⋮ A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs ⋮ Distinguished Minimal Topological Lassos ⋮ On general frameworks and threshold functions for multiple domination ⋮ Domatically full Cartesian product graphs ⋮ Trees with 2-reinforcement number three

Uses Software

GRAFFITI

Cites Work

This page was built for publication: \(k\)-domination and \(k\)-independence in graphs: A survey