On Roman, Global and Restrained Domination in Graphs

Zverovich, Vadim; Poghosyan, Anush

Abstract

In this paper, we present new upper bounds for the global domination and Roman domination numbers and also prove that these results are asymptotically best possible. Moreover, we give upper bounds for the restrained domination and total restrained domination numbers for large classes of graphs, and show that, for almost all graphs, the restrained domination number is equal to the domination number, and the total restrained domination number is equal to the total domination number. A number of open problems are posed. © 2010 Springer.

Citation

Zverovich, V., & Poghosyan, A. (2011). On Roman, Global and Restrained Domination in Graphs. Graphs and Combinatorics, 27(5), 755-768. https://doi.org/10.1007/s00373-010-0992-z

• Journal Article Type: Article
• Publication Date: Sep 1, 2011
• Deposit Date: Sep 24, 2015
• Publicly Available Date: Feb 12, 2016
• Journal: Graphs and Combinatorics
• Print ISSN: 0911-0119
• Publisher: Springer Verlag
• Peer Reviewed: Peer Reviewed
• Volume: 27
• Issue: 5
• Pages: 755-768
• DOI: https://doi.org/10.1007/s00373-010-0992-z
• Keywords: graphs, Roman domination number, global domination number, restrained domination number
• Public URL: https://uwe-repository.worktribe.com/output/972543
• Publisher URL: http://dx.doi.org/10.1007/s00373-010-0992-z
• Additional Information: Additional Information : The final publication is available at Springer via http://dx.doi.org/10.1007/s00373-010-0992-z