Article in volume

Authors:

M. Miotk

Mateusz Miotk

*

email: mmiotk@inf.ug.edu.pl

0000-0003-2768-7861

P. Żylinski

Paweł Żylinski

University of Gdańsk

email: zylinski@inf.ug.edu.pl

0000-0001-6378-7742

Title:

Spanning trees with disjoint dominating and 2-dominating sets

Source:

Discussiones Mathematicae Graph Theory 42(1) (2022) 299-308

Received: 2019-05-14 , Revised: 2019-10-03 , Accepted: 2019-10-03 , Available online: 2019-11-13 , https://doi.org/10.7151/dmgt.2258

Abstract:

Keywords:

domination, 2-domination, spanning tree

References:

1. V. Anusuya and R. Kala, A note on disjoint dominating sets in graphs, Int. J. Contem. Math. Sci. 7 (2012) 2099–2110.
2. H. Broersma, O. Koppius, H. Tuinstra, A. Huck, T. Kloks, D. Kratsch and H. Müller, Degree-preserving trees, Networks 35 (2000) 26–39.
   https://doi.org/10.1002/(SICI)1097-0037(200001)35:1<26::AID-NET3>3.0.CO;2-M
3. F. Buckley and M. Lewinter, On graphs with center-preserving spanning tree, Graph Theory Notes N.Y. 14 (1987) 33–35.
4. F. Buckley and M. Lewinter, A note on graphs with diameter-preserving spanning trees, J. Graph Theory 12 (1988) 525–528.
   https://doi.org/10.1002/jgt.3190120408
5. F. Buckley and Z. Palka, Property preserving spanning trees in random graphs, in: Random Graphs '87, Karoński, Jaworski and Ruciński (Ed(s)), (Wiley & Sons, New York 1990) 17–28.
6. L. Cai and D.G. Corneil, Tree spanners, SIAM J. Discrete Math. 8 (1995) 359–387.
   https://doi.org/10.1137/S0895480192237403
7. G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs (CRC Press, Boca Raton, 2016).
8. P. Delgado, W.J. Desormeaux and T.W. Haynes, Partitioning the vertices of a graph into two total dominating sets, Quaest. Math. 39 (2016) 863–873.
   https://doi.org/10.2989/16073606.2016.1188862
9. W.J. Desormeaux, T.W. Haynes and M.A. Henning, Partitioning the vertices of a cubic graph into two total dominating sets, Discrete Appl. Math. 223 (2017) 52–63.
   https://doi.org/10.1016/j.dam.2017.01.032
10. S. Földes and P.L. Hammer, Split graphs, Congr. Numer. 19 (1977) 311–315.
11. M.A. Henning, Ch. Löwenstein and D. Rautenbach, Remarks about disjoint dominating sets, Discrete Math. 309 (2009) 6451–6458.
    https://doi.org/10.1016/j.disc.2009.06.017
12. M.A. Henning and D.F. Rall, On graphs with disjoint dominating and $2$-dominating sets, Discuss. Math. Graph Theory 33 (2013) 139–146.
    https://doi.org/10.7151/dmgt.1652
13. A. Kaneko and K. Yoshimoto, On spanning trees with restricted degrees, Inform. Process. Lett. 73 (2000) 163–165.
    https://doi.org/10.1016/S0020-0190(00)00018-1
14. Ch.-Ch. Lin, G.J. Chang and G.-H. Chen, The degree-preserving spanning tree problem in strongly chordal and directed path graphs, Networks 56 (2009) 183–187.
    https://doi.org/10.1002/net.20359
15. Y. Liu and J. Huang, Diameter-preserving spanning trees in sparse weighted graphs, Graphs Combin. 25 (2009) 753–758.
    https://doi.org/10.1007/s00373-010-0887-z
16. M. Miotk, J. Topp and P. Żyliński, Disjoint dominating and $2$-dominating sets in graphs, Discrete Optim. 35 (2020) 100553.
    https://doi.org/10.1016/j.disopt.2019.100553
17. I. Papoutsakis, Tree spanners of bounded degree graphs, Discrete Appl. Math. 236 (2018) 395–407.
    https://doi.org/10.1016/j.dam.2017.10.025
18. J. Southey and M.A. Henning, A characterization of graphs with disjoint dominating and paired-dominating sets, J. Comb. Optim. 22 (2011) 217–234.
    https://doi.org/10.1007/s10878-009-9274-1
19. J. Southey and M.A. Henning, Dominating and total dominating partitions in cubic graphs, Cent. Eur. J. Math. 9 (2011) 699–708.
    https://doi.org/10.2478/s11533-011-0014-2