k-domination and k-independence in graphs: A survey

DOI10.1007/S00373-011-1040-3zbMATH Open1234.05174OpenAlexW2017926358MaRDI QIDQ659765FDOQ659765

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

Recommendations

• scientific article; zbMATH DE number 2544
• Independent domination in graphs: A survey and recent results
• On \(k\)-domination and \(j\)-independence in graphs
• scientific article
• On the \(k\)-independence number in graphs

zbMATH Keywords

\(k\)-independence\(k\)-tuple domination\(k\)-dominationconnected \(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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On a conjecture of Fink and Jacobson concerning k-domination and k- dependence
• On the ratio of optimal integral and fractional covers
• Roman domination in graphs.
• Transversal numbers of uniform hypergraphs
• Bounds on the \(k\)-domination number of a graph
• On \(k\)-domination and \(j\)-independence in graphs
• Some bounds on the \(p\)-domination number in trees
• On the corona of two graphs
• Trees with unique minimum \(p\)-dominating sets
• Independence andk-domination in graphs
• Onk-domination and minimum degree in graphs
• Extremal Problems for Roman Domination
• Title not available (Why is that?)
• Domination-balanced graphs
• Improved lower bounds on k‐independence
• Title not available (Why is that?)
• Connected Domination and Spanning Trees with Many Leaves
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the domination number of a random graph
• Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Title not available (Why is that?)
• On the residue of a graph
• Towards a theory of domination in graphs
• On the p-domination number of cactus graphs
• On domination and independent domination numbers of a graph
• The roman domatic number of a graph
• Title not available (Why is that?)
• \(k\)-tuple domination in graphs
• An upper bound for thek-domination number of a graph
• Title not available (Why is that?)
• On graphs having domination number half their order
• Relations between packing and covering numbers of a tree
• Title not available (Why is that?)
• ROMAN k-DOMINATION IN GRAPHS
• On Hadwiger's Number and the Stability Number
• Title not available (Why is that?)
• New bounds on the \(k\)-domination number and the \(k\)-tuple domination number
• Title not available (Why is that?)
• k-Independence and thek-residue of a graph
• A generalization of maximal independent sets
• The k-domatic number of a graph
• Title not available (Why is that?)
• Nordhaus-Gaddum inequalities for domination in graphs
• On graphs with equal domination and 2-domination numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ratios of some domination parameters in trees
• Characterizations of trees with equal paired and double domination numbers
• Title not available (Why is that?)
• A new domination conception
• Title not available (Why is that?)
• A note on the k-domination number of a graph
• Title not available (Why is that?)
• On the \(k\)-tuple domination of de Bruijn and Kautz digraphs
• On conjectures of Graffiti
• A note on Nordhaus-Gaddum inequalities for domination.
• Title not available (Why is that?)
• Bounds on the upper \(k\)-domination number and the upper \(k\)-star-forming number of a graph
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• Characterization of graphs with equal domination and covering number
• Trees with two disjoint minimum independent dominating sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Upper bounds for \(f\)-domination number of graphs
• A generalised upper bound for the \(k\)-tuple domination number
• 3-Tuple domination number in complete grid graphs
• On Double Domination in Graphs
• The \(k\)-tuple domination number revisited
• Proof of a conjecture on \(k\)-tuple domination in graphs
• Dominating a family of graphs with small connected subgraphs
• On \(k\)-independence in graphs with emphasis on trees
• Title not available (Why is that?)
• Bounds on the connected \(k\)-domination number in graphs
• Contributions to the theory of domination, independence and irredundance in graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on the p-domination number of trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• On \(k\)-dependent domination
• A general method in the theory of domination in graphs
• Title not available (Why is that?)
• 2-domination subdivision number of graphs
• The insulation sequence of a graph
• Perfect stables in graphs
• \(H\)-forming sets in graphs
• A note on the double domination number in trees
• An alternative definition of the \(k\)-irredundance
• On a relationship between 2-dominating and 5-dominating sets in graphs
• Characterization of trees with equal 2-domination number and domination number plus two
• On 2-domination and independence domination numbers of graphs.
• A characterization of (γ_t,γ₂)-trees
• Title not available (Why is that?)
• On the (2,2)-domination number of trees
• k-independence stable graphs upon edge removal
• A bound on the k-domination number of a graph
• Bounds on the k-tuple domatic number of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• On $k$-domatic numbers of graphs
• BOUNDS ON THE DOMINATION NUMBER OF A GRAPH
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Nordhaus-Gaddum-type result for the 2-domination number
• Title not available (Why is that?)
• Maximal k-independent sets in graphs
• A realization algorithm for double domination in graphs
• Title not available (Why is that?)
• A remark on the (2,2)-domination number
• Title not available (Why is that?)
• Title not available (Why is that?)
• On \(k\)-star-forming sets in graphs
• Lower bounds on the \(p\)-domination number in terms of cycles and matching number
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On $f$-domination number of a graph
• Title not available (Why is that?)
• Inequalities involving independence domination, f-domination, connected and total f-domination numbers
• Title not available (Why is that?)
• Claw-free graphs with equal 2-domination and domination numbers
• Title not available (Why is that?)
• Graphs with double domination numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Characterization of block graphs with equal 2-domination number and domination number plus one
• Title not available (Why is that?)
• Exact double domination in graphs
• Some results on total domination in direct products of graphs
• On domination and annihilation in graphs with claw-free blocks
• Graphs whose vertex independence number is unaffected by single edge addition or deletion
• Onk-tuple domination of random graphs
• Restrained double domination number of a graph

Cited In (91)

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

Uses Software

• GRAFFITI

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659765)