Distance domination, guarding and vertex cover for maximal outerplanar graph

2013/07/08 by Santiago Canales, Gregorio Hernández Peñalver, Canales, Santiago +7
Computer Science · Materials Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Graphene research and applications #Interconnection Networks and Systems #cs.CG

paper · pdf · doi:10.48550/arxiv.1307.2043

arxiv created 2013/07/08 · openalex publication_date 2013/07/08 · arxiv updated 2013/07/09 · openalex created_date 2022/08/30 · openalex updated_date 2026/07/28

Abstract

This paper discusses a distance guarding concept on triangulation graphs, which can be associated with distance domination and distance vertex cover. We show how these subjects are interconnected and provide tight bounds for any n-vertex maximal outerplanar graph: the 2d-guarding number, g_2d(n) = n/5; the 2d-distance domination number, gamma_2d(n) = n/5; and the 2d-distance vertex cover number, beta_2d(n) = n/4.

Related

• Dominating maximal outerplane graphs and Hamiltonian plane triangulations
• Eternal vertex cover number of maximal outerplanar graphs
• Domination, Eternal Domination, and Clique Covering
• Eternal distance-k domination on graphs
• Some considerations on the maximal safety distance in a graph