Convex dominating sets in maximal outerplanar graphs

DOI10.1016/J.DAM.2019.02.029MaRDI QIDQ2312656zbMATH OpenOpenAlexFDO

Authors E. Rivera-Campo, Radosław Ziemann, Rita Zuazua, Paweł Żyliński, Magdalena Lemańska

Publication date 17 July 2019

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

Full work available at URL https://doi.org/10.1016/j.dam.2019.02.029

zbMATH Keywords

outerplanarconvex dominationconvex guard setflipping edge

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Combinatorial bounds on connectivity for dominating sets in maximal outerplanar graphs
• Total dominating sets in maximal outerplanar graphs
• Dominating sets of maximal outerplanar graphs
• Distance domination, guarding and covering of maximal outerplanar graphs
• Bounds for the connected domination number of maximal outerplanar graphs

Cites work

• scientific article; zbMATH DE number 6096635 (Why is no real title available?)
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 4103086 (Why is no real title available?)
• scientific article; zbMATH DE number 3702724 (Why is no real title available?)
• scientific article; zbMATH DE number 167883 (Why is no real title available?)
• scientific article; zbMATH DE number 2204178 (Why is no real title available?)
• A combinatorial theorem in plane geometry
• A proof of the orbit conjecture for flipping edge-labelled triangulations
• A short proof of Chvatal's Watchman Theorem
• Algorithmic Aspects of Vertex Elimination on Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Computing the flip distance between triangulations
• Constructing connected bicritical graphs with edge-connectivity 2
• Convex domination in the composition and Cartesian product of graphs.
• Distance \(k\)-domination, distance \(k\)-guarding, and distance \(k\)-vertex cover of maximal outerplanar graphs
• Distance domination, guarding and covering of maximal outerplanar graphs
• Dominating sets in planar graphs
• Dominating sets of maximal outerplanar graphs
• Edge criticality in secure graph domination
• Enumerating pseudo-triangulations in the plane
• Flip distance between two triangulations of a point set is NP-complete
• Flipping edge-labelled triangulations
• Flips in planar graphs
• Galleries need fewer mobile guards: A variation on Chvatal's theorem
• Graphs with convex domination number close to their order
• Guarding Art Galleries: The Extra Cost for Sculptures Is Linear
• Influence of edge subdivision on the convex domination number
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Linear-time computation of optimal subgraphs of decomposable graphs
• Monitoring maximal outerplanar graphs
• Nordhaus-Gaddum results for the convex domination number of a graph
• On dominating sets of maximal outerplanar graphs
• On the secure domination numbers of maximal outerplanar graphs
• Practical algorithms on partial k-trees with an application to domination-like problems
• The complexity of first-order and monadic second-order logic revisited
• The convex domination subdivision number of a graph
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The number of caterpillars
• Total dominating sets in maximal outerplanar graphs
• Total domination edge critical graphs with total domination number three and many dominating pairs
• Total domination in maximal outerplanar graphs. II.
• Weakly convex and convex domination numbers of some products of graphs.

Cited in

(5)

• THE FORCING CONVEX DOMINATION NUMBER OF A GRAPH
• On dominating sets of maximal outerplanar graphs
• On the general position numbers of maximal outerplane graphs
• On dominating sets of maximal outerplanar and planar graphs
• Total domination in plane triangulations

This page was built for publication: Convex dominating sets in maximal outerplanar graphs

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