Maximal outerplanar graphs with semipaired domination number double the domination number

Document Type : Original paper

Authors

1 Department of Mathematics and Applied Mathematics, University of Johannesburg

2 Department of Mathematics, King Mongkut's University of Technology Thonburi

Abstract

A subset $S$ of vertices in a graph $G$ is a dominating set if every vertex in $V(G) \setminus S$ is adjacent to a vertex in $S$. If the graph $G$ has no isolated vertex, then a pair dominating set $S$ of $G$ is a dominating set of $G$ such that $G[S]$ has a perfect matching. Further, a semipaired dominating set of $G$ is a dominating set of $G$ with the additional property that the set $S$ can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The domination number $\gamma(G)$ is the minimum cardinality of a dominating set of $G$. Similarly, the paired (semipaired) domination number $\gamma_{pr}(G)$ $(\gamma_{pr2}(G))$ is the minimum cardinality of a paired (semipaired) dominating set of $G$. It is known that for a graph $G$, $\gamma(G) \le \gamma_{pr2}(G) \le \gamma_{pr}(G) \le 2\gamma(G)$. In this paper, we characterize maximal outerplanar graphs $G$ satisfying $\gamma_{pr2}(G) = 2\gamma(G)$. Hence, our result yields the characterization of maximal outerplanar graphs $G$ satisfying $\gamma_{pr}(G) = 2\gamma(G)$.

Keywords

Main Subjects

References

[1] B. Allgeier, Structure and properties of maximal outerplanar graphs, Ph.D. thesis, 2009.
[2] W.J. Desormeaux, T.W. Haynes, and M.A. Henning, Paired Domination in Graphs, pp. 31–77, Springer International Publishing, Cham, 2020.
[3] W.J. Desormeaux and M.A. Henning, Paired domination in graphs: a survey and recent results, Util. Math. 94 (2014), 101–166.
[4] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Topics in Domination in Graphs, vol. 64, Springer, Cham, 2020.
[5] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Structures of Domination in Graphs, vol. 66, Springer, Cham, 2021.
[6] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Core Concepts, Springer, Cham, 2023.
[7] T.W. Haynes and M.A. Henning, Perfect graphs involving semitotal and semipaired domination, J. Comb. Optim. 36 (2018), no. 2, 416–433.
https://doi.org/10.1007/s10878-018-0303-9
[8] T.W. Haynes and M.A. Henning, Semipaired domination in graphs, J. Combin. Comput. Combin. Math. 104 (2018), 93–109.
[9] T.W. Haynes and M.A. Henning, Graphs with large semipaired domination number, Discuss. Math. Graph Theory 39 (2019), no. 3, 659–671.
https://doi.org/10.7151/dmgt.2143
[10] T.W. Haynes and M.A. Henning, Trees with unique minimum semitotal dominating sets, Graphs Combin. 36 (2020), no. 3, 689–702.
https://doi.org/10.1007/s00373-020-02145-0
[11] T.W. Haynes and M.A. Henning, Bounds on the semipaired domination number of graphs with minimum degree at least two, J. Comb. Optim. 41 (2021), no. 2, 451–486.
https://doi.org/10.1007/s10878-020-00687-w
[12] T.W. Haynes and M.A. Henning, Construction of trees with unique minimum semipaired dominating sets, J. Combin. Math. Combin. Comput. 116 (2021), 1–12.
[13] T.W. Haynes and P.J. Slater, Paired-domination and the paired-domatic number, T.W. Haynes and M.A. Henning
Congr. Numer. 109 (1995), 65–72.
[14] T.W. Haynes and P.J. Slater, Paired-domination in graphs, Networks 32 (1998), no. 3, 199–206.
[15] M.A. Henning, A. Pandey, and V. Tripathi, Complexity and algorithms for semipaired domination in graphs, Theory Comput. Syst. 64 (2020), no. 7, 1225–1241.
https://doi.org/10.1007/s00224-020-09988-3
[16] T.W. Haynes and P.J. Slater, Complexity and algorithms for semipaired domination in graphs, Theory Comput. Syst. 64 (2020), no. 7, 1225–1241.
https://doi.org/10.1007/s00224-020-09988-3
[17] M. Lemańska, R. Zuazua, and P. Żyliński, Total dominating sets in maximal outerplanar graphs, Graphs Combin. 33 (2017), no. 4, 991–998.
https://doi.org/10.1007/s00373-017-1802-7
[18] J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, New York, 1987.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 18 April 2024

Files

Share

How to cite

Statistics