Connected Domination

DOI10.1007/978-3-030-51117-3_4zbMath1479.05254MaRDI QIDQ3384607

Mustapha Chellali, Odile Favaron

Publication date: 15 December 2021

Published in: Topics in Domination in Graphs (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-51117-3_4

zbMATH Keywords

connected dominating set

Mathematics Subject Classification ID

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

A proof of a conjecture on the connected domination number, Leafy spanning \(k\)-forests, Disprove of a conjecture on the doubly connected domination subdivision number

Cites Work

• Complexity of the maximum leaf spanning tree problem on planar and regular graphs
• The price of connectivity for dominating set: upper bounds and complexity
• Improved bounds for spanning trees with many leaves
• Max-leaves spanning tree is APX-hard for cubic graphs
• On graphs for which the connected domination number is at most the total domination number
• Connected dominating set. Theory and applications
• Domination alteration sets in graphs
• Inequalities of Nordhaus-Gaddum type for doubly connected domination number
• Bounds on the connected \(k\)-domination number in graphs
• Connected domination number of a graph and its complement
• A greedy approximation for minimum connected dominating sets
• Spanning trees with many leaves: new lower bounds in terms of the number of vertices of degree 3 and at least 4
• Spanning trees with many leaves: lower bounds in terms of the number of vertices of degree 1, 3 and at least 4
• Arbres avec un nombre maximum de sommets pendants
• Domination dot-critical graphs
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Distance irredundance and connected domination numbers of a graph
• Total domination of graphs and small transversals of hypergraphs
• Bounds relating the weakly connected domination number to the total domination number and the matching number
• On an open problem concerning total domination critical graphs
• A survey of selected recent results on total domination in graphs
• Spanning trees with many leaves and average distance
• A constructive characterization of total domination vertex critical graphs
• Complete description of forbidden subgraphs in the structural domination problem
• Clustering and domination in perfect graphs
• An extremal problem for edge domination insensitive graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Some inequalities about connected domination number
• Constructing full spanning trees for cubic graphs
• Unit disk graphs
• Permutation graphs: Connected domination and Steiner trees
• Spanning trees in graphs of minimum degree 4 or 5
• On connected cutfree domination in graphs
• The complexity of domination problems in circle graphs
• Relations between packing and covering numbers of a tree
• On graphs with equal domination and connected domination numbers
• On weakly connected domination in graphs
• Approximation algorithms for connected dominating sets
• 2-connected graphs with small 2-connected dominating sets.
• Some results related to the toughness of 3-domination critical graphs
• On connected \(k\)-domination numbers of graphs.
• Extremal graphs for inequalities involving domination parameters
• Characterization of graphs with equal domination and covering number
• Making a dominating set of a graph connected
• Hamiltonicity, minimum degree and leaf number
• Domination parameters of a graph and its complement
• Leaf number and Hamiltonian \(C_4\)-free graphs
• Some results on the independence number of connected domination critical graphs
• Graphs with forbidden subgraphs and leaf number
• Spanning paths in graphs
• Average eccentricity, \(k\)-packing and \(k\)-domination in graphs
• Characterization of graphs with equal domination and connected domination numbers
• Connected domination critical graphs.
• On the number of edges in graphs with a given weakly connected domination number
• Bounds of the number of leaves of spanning trees in graphs without triangles
• Bounds of the number of leaves of spanning trees
• A survey of Nordhaus-Gaddum type relations
• The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
• A characterization of \(3\)-\((\gamma _{c}, 2)\)-critical claw-free graphs which are not \(3\)-\(\gamma _{c }\)-critical
• On the number of edges in graphs with a given connected domination number
• Connected domination game played on Cartesian products
• Connected domination in maximal outerplanar graphs
• Connected domination critical graphs with cut vertices
• Distance domination and distance irredundance in graphs
• Upper bounds on the average eccentricity
• Bounds on the connected domination number of a graph
• Matching properties in connected domination critical graphs
• On graphs with equal total domination and connected domination numbers
• On the doubly connected domination number of a graph
• On weakly connected domination in graphs. II.
• Traceability of connected domination critical graphs
• Connected Domination Stable Graphs Upon Edge Addition
• Spanning trees with many leaves in cubic graphs
• A general method in the theory of domination in graphs
• Weakly connected domination stable trees
• Domination on Cocomparability Graphs
• Spanning Trees with Many Leaves
• Connected Domatic Number in Planar Graphs
• Hereditary Domination in Graphs: Characterization with Forbidden Induced Subgraphs
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• On Hadwiger's Number and the Stability Number
• Steiner trees, connected domination and strongly chordal graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Vertex domination-critical graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Perfect connected-dominant graphs
• Connected Domination and Spanning Trees with Many Leaves
• Graphs without induced P₅and C₅
• Vertex domination‐critical graphs
• Hamilton cycles in split graphs with large minimum degree
• Connected domination game
• Lower bounds on the leaf number in graphs with forbidden subgraphs
• Doubly chordal graphs, steiner trees, and connected domination
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
• Domination Numbers in Graphs with Removed Edge or Set of Edges
• Size, Order, and Connected Domination
• On domination critical graphs with cutvertices having connected domination number 3
• Spanning trees with many leaves
• Domination critical graphs
• 2-edge connected dominating sets and 2-connected dominating sets of a graph
• 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