Article in volume
Authors:
Baoyindureng Wu
College of Mathematics and System SciencesXinjiang UniversityUrumqi 830046P.R. CHINA
email: baoywu@163.com
Title:
Outer connected domination in maximal outerplanar graphs and beyond
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 575-590
Received: 2022-01-24 , Revised: 2022-05-14 , Accepted: 2022-05-27 , Available online: 2022-06-28 , https://doi.org/10.7151/dmgt.2462
Abstract:
A set $S$ of vertices in a graph $G$ is an outer connected dominating set of
$G$ if every vertex in $V\setminus S$ is adjacent to a vertex in $S$ and the
subgraph induced by $V\setminus S$ is connected. The outer connected domination
number of $G$, denoted by $\tilde{\gamma_{c}}(G)$, is the minimum cardinality
of an outer connected dominating set of $G$. Zhuang [Domination and outer
connected domination in maximal outerplanar graphs, Graphs Combin. 37 (2021)
2679–2696] recently proved that $\tilde{\gamma_{c}}(G)\leq\left\lfloor
\frac{n+k}{4} \right\rfloor$ for any maximal outerplanar graph $G$ of order $n\geq 3$
with $k$ vertices of degree 2 and posed a conjecture which states that $G$ is a
striped maximal outerplanar graph with $\tilde{\gamma_{c}}(G)=\left\lfloor
\frac{n+2}{4}\right\rfloor$ if and only if $G\in \mathfrak{\mathcal{A}}$, where
$\mathcal{A}$ consists of six special families of striped outerplanar graphs.
We disprove the conjecture. Moreover, we show that the conjecture become valid
under some additional property to the striped maximal outerplanar graphs. In
addition, we extend the above theorem of Zhuang to all maximal $K_{2,3}$-minor
free graphs without $K_4$ and all $K_4$-minor free graphs.
Keywords:
maximal outerplanar graphs, outer connected domination, striped maximal outerplanar graphs
References:
- M.H. Akhbari, R. Hasni, O. Favaron, H. Karami and S.M. Sheikholeslami, On the outer-connected domination in graphs, J. Comb. Optim. 26 (2013) 10–18.
https://doi.org/10.1007/s10878-011-9427-x - S. Alikhani, M.H. Akhbari, C. Eslahchi and R. Hasni, On the number of outer connected dominating sets of graphs, Util. Math. 91 (2013) 99–107.
- T. Araki and I. Yumoto, On the secure domination numbers of maximal outerplanar graphs, Discrete Appl. Math. 236 (2018) 23–29.
https://doi.org/10.1016/j.dam.2017.10.020 - J.A. Bondy and U.S.R. Murty, Graph Theory, in: Grad. Texts in Math. 244 (Springer, New York, 2008).
- P. Borg and P. Kaemawichanurat, Partial domination of maximal outerplanar graphs, Discrete Appl. Math. 283 (2020) 306–314.
https://doi.org/10.1016/j.dam.2020.01.005 - C.N. Campos and Y. Wakabayashi, On dominating sets of maximal outerplanar graphs, Discrete Appl. Math. 161 (2013) 330–335.
https://doi.org/10.1016/j.dam.2012.08.023 - J. Cyman, The outer-connected domination number of a graph, Australas. J. Combin. 38 (2007) 35–46.
- M. Dorfling, J.H. Hattingh and E. Jonck, Total domination in maximal outerplanar graphs II, Discrete Math. 339 (2016) 1180–1188.
https://doi.org/10.1016/j.disc.2015.11.003 - M. Dorfling, J.H. Hattingh and E. Jonck, Total domination in maximal outerplanar graphs, Discrete Appl. Math. 217 (2017) 506–511.
https://doi.org/10.1016/j.dam.2016.10.020 - M.A. Henning and P. Kaemawichanurat, Semipaired domination in maximal outerplanar graphs, J. Comb. Optim. 38 (2019) 911–926.
https://doi.org/10.1007/s10878-019-00427-9 - H. Jiang and E. Shan, Outer-connected domination in graphs, Util. Math. 81 (2010) 265–274.
- Z. Li, E. Zhu, Z. Shao and J. Xu, On dominating sets of maximal outerplanar and planar graphs, Discrete Appl. Math. 198 (2016) 164–169.
https://doi.org/10.1016/j.dam.2015.06.024 - D. Pradhan, On the complexity of the minimum outer-connected dominating set problem in graphs, J. Comb. Optim. 31 (2016) 1–12.
https://doi.org/10.1007/s10878-013-9703-z - S.-i. Tokunaga, Dominating sets of maximal outerplanar graphs, Discrete Appl. Math. 161 (2013) 3097–3099.
https://doi.org/10.1016/j.dam.2013.06.025 - S. Wang, B. Wu, X. An, X. Liu and X. Deng, Outer-connected dominationin in $2$-connected cubic graphs, Discrete Math. Algorithms Appl. 6 (2014) 1450032.
https://doi.org/10.1142/S1793830914500323 - T. Zhu and B. Wu, Domination of maximal $K_4$-minor free graphs and maximal $K_{2,3}$-minor free graphs, and disproofs of two conjectures on planar graphs, Discrete Appl. Math. 194 (2015) 147–153.
https://doi.org/10.1016/j.dam.2015.05.029 - W. Zhuang, Domination and outer connected domination in maximal outerplanar graphs, Graphs Combin. 37 (2021) 2679–2696.
https://doi.org/10.1007/s00373-021-02383-w - W. Zhuang, Connected domination in maximal outerplanar graphs, Discrete Appl. Math. 283 (2020) 533–541.
https://doi.org/10.1016/j.dam.2020.01.033
Close