Premium
Dominating sets inducing large components in maximal outerplanar graphs
Author(s) -
Alvarado José D.,
Dantas Simone,
Rautenbach Dieter
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22217
Subject(s) - mathematics , combinatorics , outerplanar graph , discrete mathematics , graph , order (exchange) , pathwidth , integer (computer science) , line graph , finance , economics , computer science , programming language
For a maximal outerplanar graph G of order n at least three, Matheson and Tarjan showed that G has domination number at most n / 3 . Similarly, for a maximal outerplanar graph G of order n at least five, Dorfling, Hattingh, and Jonck showed, by a completely different approach, that G has total domination number at most 2 n / 5 unless G is isomorphic to one of two exceptional graphs of order 12. We present a unified proof of a common generalization of these two results. For every positive integer k , we specify a set H k of graphs of order at least 4 k + 4 and at most 4 k 2 − 2 k such that every maximal outerplanar graph G of order n at least 2 k + 1 that does not belong to H k has a dominating set D of order at most ⌊ k n 2 k + 1 ⌋ such that every component of the subgraph G [ D ] of G induced by D has order at least k .