Geodesic
Outer connected domination in maximal outerplanar graphs and beyond
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 575-590 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A set S of vertices in a graph G is an outer connected dominating set of G if every vertex in V∖ S is adjacent to a vertex in S and the subgraph induced by V∖ S is connected. The outer connected domination number of G, denoted by γ̃_̃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 γ̃_̃c̃(G)≤⌊n+k4⌋ for any maximal outerplanar graph G of order n≥ 3 with k vertices of degree 2 and posed a conjecture which states that G is a striped maximal outerplanar graph with γ̃_̃c̃(G)=⌊n+24⌋ if and only if G∈𝒜, where 𝒜 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 
@article{DMGT_2024_44_2_a8,
     author = {Yang, Wei and Wu, Baoyindureng},
     title = {Outer connected domination in maximal outerplanar graphs and beyond},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {575--590},
     year = {2024},
     volume = {44},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a8/}
}
TY  - JOUR
AU  - Yang, Wei
AU  - Wu, Baoyindureng
TI  - Outer connected domination in maximal outerplanar graphs and beyond
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 575
EP  - 590
VL  - 44
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a8/
LA  - en
ID  - DMGT_2024_44_2_a8
ER  - 
%0 Journal Article
%A Yang, Wei
%A Wu, Baoyindureng
%T Outer connected domination in maximal outerplanar graphs and beyond
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 575-590
%V 44
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a8/
%G en
%F DMGT_2024_44_2_a8
Yang, Wei; Wu, Baoyindureng. Outer connected domination in maximal outerplanar graphs and beyond. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 575-590. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a8/

[1] 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

[2] 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.

[3] 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

[4] J.A. Bondy and U.S.R. Murty, Graph Theory, in: Grad. Texts in Math. 244 (Springer, New York, 2008).

[5] 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

[6] 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

[7] J. Cyman, The outer-connected domination number of a graph, Australas. J. Combin. 38 (2007) 35–46.

[8] 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

[9] 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

[10] 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

[11] H. Jiang and E. Shan, Outer-connected domination in graphs, Util. Math. 81 (2010) 265–274.

[12] 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

[13] 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

[14] 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

[15] 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

[16] T. Zhu and B. Wu, Domination of maximal K4-minor free graphs and maximal K2,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

[17] 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

[18] 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