Bibliography on domination in graphs and some basic definitions of domination parameters

DOI10.1016/0012-365X(90)90365-OzbMath0733.05076OpenAlexW1975119263MaRDI QIDQ810066

Stephen T. Hedetniemi, Renu C. Laskar

Publication date: 1990

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(90)90365-o

zbMATH Keywords

bibliographyindependence numberdominating setdomination number

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (05C99) Bibliographies for mathematics in general (00A15)

Related Items

A sufficient condition for kernel perfectness of a digraph in terms of semikernels modulo \(F\), Isolation of \(k\)-cliques. II, Weighted efficient domination problem on some perfect graphs, Irredundance perfect graphs, Domination in graphoidally covered graphs: least-kernel graphoidal graphs. II, Strong weak domination and domination balance in a graph, Domination and irredundance in the queens' graph, On the domination number of cross products of graphs, Closed neighborhood ideals of finite simple graphs, CONVEXITY OF MINIMAL DOMINATING FUNCTIONS OF TREES: A SURVEY, ON WEAK DOMINATION NUMBER OF SOME GRAPHS, SOME RESULTS ON WEAK DOMINATION IN GRAPHS, Domination and upper domination of direct product graphs, Decreasing the maximum degree of a graph, The e-mail gossip number and the connected domination number, A linear-time algorithm for weighted paired-domination on block graphs, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Unnamed Item, Isolation of cycles, Nordhaus-Gaddum inequalities for domination in graphs, Isolation of \(k\)-cliques, Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA, On the domination number of $t$-constrained de Bruijn graphs, Isolation of connected graphs, Unions of digraphs which become kernel perfect, Convexity of minimal total dominating functions in graphs, The domination numbers of cylindrical grid graphs, Domination in direct products of complete graphs, Secure equitability in graphs, Extensions of the Art Gallery Theorem, On bondage numbers of graphs: a survey with some comments, Edge domination in some path and cycle related graphs, On generalised minimal domination parameters for paths, A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees, The product of the independent domination numbers of a graph and its complement, An optimal algorithm to find minimum k-hop dominating set of interval graphs, Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics, Bounds on the size of the minimum dominating sets of some cylindrical grid graphs, Paired-domination problem on distance-hereditary graphs, Some results on universal minimal total dominating functions, Domination in distance-hereditary graphs, The domination complexity and related extremal values of large 3D torus, Data Exploration by Representative Region Selection: Axioms and Convergence, Upper and lower bounds on approximating weighted mixed domination, Domination number of an interval catch digraph family and its use for testing uniformity, Dominating sets in finite generalized quadrangles, Admissible property of graphs in terms of independence number, Real and integer domination in graphs, Irredundant and perfect neighbourhood sets in trees, On independent domination number of regular graphs, An upper bound for the independent domination number, Linear programming formulation for some generalized domination parameters, The sequence of upper and lower domination, independence and irredundance numbers of a graph, Minimum r-neighborhood covering set of permutation graphs, An algorithm for prescribed multiple domination in arbitrary graphs, A linear-time algorithm for paired-domination on circular-arc graphs, Convexity of minimal dominating functions of trees. II, On Congruent Domination Number of Disjoint and One Point Union of Graphs

Cites Work

• Domination alteration sets in graphs
• Matchings and transversals in hypergraphs, domination and independence in trees
• On the computational complexity of upper fractional domination
• On domination and independent domination numbers of a graph
• On kernels and semikernels of digraphs
• Domination, independent domination, and duality in strongly chordal graphs
• The irredundance number and maximum degree of a graph
• Dominating sets for split and bipartite graphs
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• Gallai theorems for graphs, hypergraphs, and set systems
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
• Estimations for the domination number of a graph
• On the independent queens covering problem
• Characterizations of strongly chordal graphs
• The neighbourhood number of a graph
• Finding minimum dominating cycles in permutation graphs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• A note on total domination
• Dominating sets and domatic number of circular arc graphs
• Clustering and domination in perfect graphs
• On a conjecture of Fink and Jacobson concerning k-domination and k- dependence
• On the diagonal queens domination problem
• A linear algorithm for finding a minimum dominating set in a cactus
• A theorem about a conjecture of H. Meyniel on kernel-perfect graphs
• Domination parameters for the bishops graph
• On graphs having domination number half their order
• Structure and recognition of domishold graphs
• Bipartite permutation graphs
• Line domination in graphs
• On the sum of two parameters concerning independence and irredundance in a graph
• A sufficient condition for dominating cycles
• An extremal problem for edge domination insensitive graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• On domination problems for permutation and other graphs
• A note on distance-dominating cycles
• A unified approach to domination problems on interval graphs
• Total domination in interval graphs revisited
• An efficient algorithm for maxdominance, with applications
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Labeling algorithms for domination problems in sun-free chordal graphs
• Finding a minimum independent dominating set in a permutation graph
• On the product of upper irredundance numbers of a graph and its complement
• Inequalities between the domination number and the chromatic number of a graph
• Total domination in block graphs
• Contributions to the theory of domination, independence and irredundance in graphs
• Indominable graphs cannot be characterised by a family of forbidden subgraphs
• The distance-domination numbers of trees
• Complexity of finding k-path-free dominating sets in graphs
• Independent domination in chordal graphs
• R-domination of block graphs
• Existence of dominating cycles and paths
• Chessboard domination problems
• On the queen domination problem
• The bondage number of a graph
• Chordal graphs and upper irredundance, upper domination and independence
• Regular totally domatically full graphs
• Domatically critical and domatically full graphs
• On generalised minimal domination parameters for paths
• Covering all cliques of a graph
• The least point covering and domination numbers of a graph
• Dominating sets in perfect graphs
• Unit disk graphs
• Permutation graphs: Connected domination and Steiner trees
• The discipline number of a graph
• Dominating cycles in Halin graphs
• On minimum dominating sets with minimum intersection
• Irredundance number versus domination number
• Lower Ramsey numbers for graphs
• An optimal algorithm for finding dominating cycles in circular-arc graphs
• A linear algorithm for the domination number of a tree
• Relations between packing and covering numbers of a tree
• Disjoint independent dominating sets in graphs
• Quasi-kernels of minimum weakness in a graph
• Optimum domination in weighted trees
• Bounds for the covering number of a graph
• Linear algorithms on recursive representations of trees
• On the sum of cardinalities of extremum maximal independent sets
• Chromatic partitions of a graph
• The sequence of upper and lower domination, independence and irredundance numbers of a graph
• On domination and independence numbers of graphs
• On kernels in i-triangulated graphs
• A linear algorithm for the domination number of a series-parallel graph
• Perfect stables in graphs
• Critical concepts in domination
• On covering sets and error-correcting codes
• Best location of service centers in a treelike network under budget constraints
• Factor domination in graphs
• Irredundant ramsey numbers for graphs
• Domination on Cocomparability Graphs
• Graph-theoretic parameters concerning domination, independence, and irredundance
• On Kernels of Graphs and Solutions of Games: A Synopsis Based on Relations and Fixpoints
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dominating cliques in graphs
• The NP-completeness column: An ongoing guide
• Total domination in interval graphs
• Total domination in interval graphs
• Domination critical graphs
• Domination critical graphs
• Covering, Packing and Generalized Perfection
• Some Packing Problems
• Decomposition of Finite Graphs into Open Chains
• Two algorithms for determining a minimum independent dominating set
• Edge-domatic number of a graph
• On $k$-domatic numbers of graphs
• Partial Complement of a Graph
• The bigraph decomposition number of a graph
• Domination in graphs with minimum degree two
• The Maximum Coverage Location Problem
• Domatically cocritical graphs
• On the Fractional Solution to the Set Covering Problem
• On Hadwiger's Number and the Stability Number
• A NEW UPPER BOUND FOR THE DOMINATION NUMBER OF A GRAPH
• A Best Possible Heuristic for the k-Center Problem
• A Linear Recognition Algorithm for Cographs
• Bichromaticity and domatic number of a bipartite graph
• On the Algorithmic Complexity of Total Domination
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Steiner trees, connected domination and strongly chordal graphs
• On the domination of the products of graphs II: Trees
• Domination in permutation graphs
• Stability, domination and irredundance in a graph
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Domination and location in acyclic graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Total Domination and Irredundance in Weighted Interval Graphs
• Vertex domination-critical graphs
• An upper bound on the domination number of a graph.
• An upper bound for thek-domination number of a graph
• Domination theory and the crapo β-invariant
• A Class of Polynomially Solvable Set-Covering Problems
• Enclaveless sets and MK-Systems
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Minimum dominating cycles in 2-trees
• Total domination in graphs
• Edge Dominating Sets in Graphs
• Partitioning trees: Matching, domination, and maximum diameter
• Some remarks on domatic numbers of graphs
• Minimum dominating cycles in outerplanar graphs
• Dominating Sets in Chordal Graphs
• Domination-balanced graphs
• R -Domination in Graphs
• Computation of Dominating Partitions
• On Spanning and Dominating Circuits in Graphs
• On kernels in strongly connected graphs
• Two-Processor Scheduling with Start-Times and Deadlines
• Linear Separation of Dominating Sets in Graphs
• Graphs with unique maximal clumpings
• Uniquely Partitionable Graphs
• Towards a theory of domination in graphs
• Packing and covering constants for certain families of trees. I
• Packing and Covering Constants for Certain Families of Trees. II
• A Characterization of Soft Hypergraphs
• Properties of Hereditary Hypergraphs and Middle Graphs
• Polygon Graph Recognition
• Linear-time computation of optimal subgraphs of decomposable graphs
• Two Bounds for the Domination Number of a Graph
• Algorithms for generalized stability numbers of tree graphs
• Dominating Set and Converse Dominating Set of a Directed Graph
• Bottleneck extrema
• On the Set-Covering Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item