آمار
| تعداد نشریات | 5 |
| تعداد شماره‌ها | 113 |
| تعداد مقالات | 1,292 |
| تعداد مشاهده مقاله | 1,267,299 |
| تعداد دریافت فایل اصل مقاله | 1,119,773 |
Maximal outerplanar graphs with semipaired domination number double the domination number | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 30 فروردین 1403 اصل مقاله (1.85 M) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2024.28972.1801 | ||
| نویسندگان | ||
| Michael A. Henning1؛ Pawaton Kaemawichanurat* 2 | ||
| 1Department of Mathematics and Applied Mathematics, University of Johannesburg | ||
| 2Department of Mathematics, King Mongkut's University of Technology Thonburi | ||
| چکیده | ||
| 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)$. | ||
| کلیدواژه‌ها | ||
| Paired-domination؛ Semipaired domination number؛ Maximal outerplanar graphs | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 168 تعداد دریافت فایل اصل مقاله: 551 |
||