Geodesic
Graphs With Large Semipaired Domination Number
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 659-671.

Voir la notice de l'article provenant de la source Library of Science

Let G be a graph with vertex set V and no isolated vertices. A subset S ⊆ V is a semipaired dominating set of G if every vertex in V \ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number γ_pr2(G) is the minimum cardinality of a semipaired dominating set of G. We show that if G is a connected graph G of order n ≥ 3, then γ_pr2 (G) ≤23 n, and we characterize the extremal graphs achieving equality in the bound.
Keywords: paired-domination, semipaired domination 
@article{DMGT_2019_39_3_a4,
     author = {Haynes, Teresa W. and Henning, Michael A.},
     title = {Graphs {With} {Large} {Semipaired} {Domination} {Number}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {659--671},
     publisher = {mathdoc},
     volume = {39},
     number = {3},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a4/}
}
TY  - JOUR
AU  - Haynes, Teresa W.
AU  - Henning, Michael A.
TI  - Graphs With Large Semipaired Domination Number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 659
EP  - 671
VL  - 39
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a4/
LA  - en
ID  - DMGT_2019_39_3_a4
ER  - 
%0 Journal Article
%A Haynes, Teresa W.
%A Henning, Michael A.
%T Graphs With Large Semipaired Domination Number
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 659-671
%V 39
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a4/
%G en
%F DMGT_2019_39_3_a4
Haynes, Teresa W.; Henning, Michael A. Graphs With Large Semipaired Domination Number. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 659-671. http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a4/

[1] W.J. Desormeaux and M.A. Henning, Paired domination in graphs: A survey and recent results, Util. Math. 94 (2014) 101–166.

[2] W. Goddard, M.A. Henning and C.A. McPillan, Semitotal domination in graphs, Util. Math. 94 (2014) 67–81.

[3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).

[4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, Inc. New York, 1998).

[5] T.W. Haynes and M.A. Henning, Semipaired domination in graphs, J. Combin. Math. Combin. Comput. 104 (2018) 93–109.

[6] T.W. Haynes and P.J. Slater, Paired-domination and the paired-domatic-number, Congr. Numer. 109 (1995) 65–72.

[7] T.W. Haynes and P.J. Slater, Paired domination in graphs Networks 32 (1998) 199–206. doi:10.1002/(SICI)1097-0037(199810)32:3h199::AID-NET4i3.0.CO;2-F

[8] M.A. Henning, Graphs with large paired-domination number, J. Comb. Optim. 13 (2007) 61–78. doi:10.1007/s10878-006-9014-8

[9] M.A. Henning, Edge weighting functions on semitotal dominating sets, Graphs Combin. 33 (2017) 403–417. doi:10.1007/s00373-017-1769-4

[10] M.A. Henning and A.J. Marcon, On matching and semitotal domination in graphs, Discrete Math. 324 (2014) 13–18. doi:10.1016/j.disc.2014.01.021

[11] M.A. Henning and A.J. Marcon, Vertices contained in all or in no minimum semitotal dominating set of a tree, Discuss. Math. Graph Theory 36 (2016) 71–93. doi:10.7151/dmgt.1844

[12] M.A. Henning and A.J. Marcon, Semitotal domination in claw-free cubic graphs, Ann. Comb. 20 (2016) 799–813. doi:10.1007/s00026-016-0331-z

[13] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013) doi:10.1007/978-1-4614-6525-6

[14] S. Huang and E. Shan, A note on the upper bound for the paired-domination number of a graph with minimum degree at least two, Networks 57 (2011) 115–116. doi:10.1002/net.20390