All Outputs (3)

Randomized algorithms and upper bounds for multiple domination in graphs and networks (2013)
Journal Article
Gagarin, A., Poghosyan, A., & Zverovich, V. (2013). Randomized algorithms and upper bounds for multiple domination in graphs and networks. Discrete Applied Mathematics, 161(4-5), 604-611. https://doi.org/10.1016/j.dam.2011.07.004

We consider four different types of multiple domination and provide new improved upper bounds for the k- and k-tuple domination numbers. They generalize two classical bounds for the domination number and are better than a number of known upper bounds... Read More about Randomized algorithms and upper bounds for multiple domination in graphs and networks.

The bondage number of graphs on topological surfaces and Teschner's conjecture (2013)
Journal Article
Zverovich, V., & Gagarin, A. (2013). The bondage number of graphs on topological surfaces and Teschner's conjecture. Discrete Mathematics, 313(6), 796-808. https://doi.org/10.1016/j.disc.2012.12.018

The bondage number of a graph is the smallest number of its edges whose removal results in a graph having a larger domination number. We provide constant upper bounds for the bondage number of graphs on topological surfaces, and improve upper bounds... Read More about The bondage number of graphs on topological surfaces and Teschner's conjecture.

Upper bounds for the bondage number of graphs on topological surfaces (2013)
Journal Article
Gagarin, A., & Zverovich, V. (2013). Upper bounds for the bondage number of graphs on topological surfaces. Discrete Mathematics, 313(11), 1132-1137. https://doi.org/10.1016/j.disc.2011.10.018

The bondage number b(G) of a graph G is the smallest number of edges of G whose removal results in a graph having the domination number larger than that of G. We show that, for a graph G having the maximum vertex degree Δ(G) and embeddable on an orie... Read More about Upper bounds for the bondage number of graphs on topological surfaces.