All Outputs (92)

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.

On Roman, Global and Restrained Domination in Graphs (2011)
Journal Article
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

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 do... Read More about On Roman, Global and Restrained Domination in Graphs.

Upper bounds for the bondage number of graphs on topological surfaces (2011)
Presentation / Conference
Zverovich, V., & Gagarin, A. (2011, July). Upper bounds for the bondage number of graphs on topological surfaces. Presented at The 23rd British Combinatorial Conference, Exeter, UK

Upper bounds for the bondage number of graphs on topological surfaces (2011)
Presentation / Conference
Zverovich, V., & Gagarin, A. (2011, May). Upper bounds for the bondage number of graphs on topological surfaces. Presented at The 7th East Coast Combinatorics Conference, Canada

Discrepancy and signed domination in graphs and hypergraphs (2010)
Journal Article
Poghosyan, A., & Zverovich, V. (2010). Discrepancy and signed domination in graphs and hypergraphs. Discrete Mathematics, 310(15-16), 2091-2099. https://doi.org/10.1016/j.disc.2010.03.030

For a graph G, a signed domination function of G is a two-colouring of the vertices of G with colours +1 and -1 such that the closed neighbourhood of every vertex contains more +1's than -1's. This concept is closely related to combinatorial discrepa... Read More about Discrepancy and signed domination in graphs and hypergraphs.

Discrepancy theory and signed domination in graphs and hypergraphs (2009)
Presentation / Conference
Zverovich, V., & Poghosyan, A. (2009, December). Discrepancy theory and signed domination in graphs and hypergraphs. Paper presented at Discrete Mathematics, Graph Theory and Their Applications, Minsk, Belarus

Upper bounds for α-domination parameters (2009)
Journal Article
Gagarin, A., Poghosyan, A., & Zverovich, V. (2009). Upper bounds for α-domination parameters. Graphs and Combinatorics, 25(4), 513-520. https://doi.org/10.1007/s00373-009-0864-6

We provide a new upper bound for the α-domination number in terms of a parameter α, 0 < α ≤ 1, and graph vertex degrees. This result generalises the well-known Caro-Roditty bound for the domination number of a graph. The same probabilistic constructi... Read More about Upper bounds for α-domination parameters.

Discrepancy and signed domination in graphs and hypergraphs (2009)
Presentation / Conference
Zverovich, V., & Poghosyan, A. (2009, July). Discrepancy and signed domination in graphs and hypergraphs. Presented at The 22nd British Combinatorial Conference, St. Andrews, Scotland, UK

The k-tuple domination number revisited (2008)
Journal Article
Zverovich, V. (2008). The k-tuple domination number revisited. Applied Mathematics Letters, 21(10), 1005-1011. https://doi.org/10.1016/j.aml.2007.10.016

The following fundamental result for the domination number γ (G) of a graph G was proved by Alon and Spencer, Arnautov, Lovász and Payan: γ (G) ≤ frac(ln (δ + 1) + 1, δ + 1) n, where n is the order and δ is the minimum degree of vertices of G. A simi... Read More about The k-tuple domination number revisited.

Upper bounds for the alpha-domination number (2008)
Presentation / Conference
Gagarin, A., Poghosyan, A., & Zverovich, V. (2008, May). Upper bounds for the alpha-domination number. Presented at The 4th East Cost Combinatorial Conference, Canada

A generalised upper bound for the k-tuple domination number (2008)
Journal Article
Gagarin, A., & Zverovich, V. (2008). A generalised upper bound for the k-tuple domination number. Discrete Mathematics, 308(5-6), 880-885. https://doi.org/10.1016/j.disc.2007.07.033

In this paper, we provide an upper bound for the k-tuple domination number that generalises known upper bounds for the double and triple domination numbers. We prove that for any graph G,γ× k (G) ≤ frac(ln (δ - k + 2) + ln (∑m = 1k - 1 (k - m) over(d... Read More about A generalised upper bound for the k-tuple domination number.

The k-tuple domination number revisited (2007)
Presentation / Conference
Zverovich, V. (2007, July). The k-tuple domination number revisited. Presented at The 21st British Combinatorial Conference, Reading, UK

A proof of Rautenbach-Volkmann’s conjecture on k-tuple domination (2006)
Presentation / Conference
domination. Paper presented at The Poznan-Zielona Gora Conference on Combinatorics, Będlewo, Poland

The Computer System GRAPHOGRAPH (2006)
Journal Article
Zverovich, V. (2006). The Computer System GRAPHOGRAPH. Electronic Notes in Discrete Mathematics, 27, 109-110. https://doi.org/10.1016/j.endm.2006.08.079

The computer system GRAPHOGRAPH (2006)
Presentation / Conference
Zverovich, V. (2006, September). The computer system GRAPHOGRAPH. Presented at ACiD - Algorithms and Complexity in Durham, Durham, UK

The computer system GRAPHOGRAPH (2006)
Presentation / Conference
Zverovich, V. (2006, May). The computer system GRAPHOGRAPH. Presented at Reading Two-Day Combinatorics Colloquium, Reading, UK

A generalised upper bound for the k-tuple domination number (2005)
Presentation / Conference
number. Presented at The 20th British Combinatorial Conference, Durham, UK

The domination parameters of cubic graphs (2005)
Journal Article
Zverovich, I. E., & Zverovich, V. (2005). The domination parameters of cubic graphs. Graphs and Combinatorics, 21(2), 277-288. https://doi.org/10.1007/s00373-005-0608-1

Let ir(G), γ(G), i(G), β0(G), Γ(G) and IR(G) be the irredundance number, the domination number, the independent domination number, the independence number, the upper domination number and the upper irredundance number of a graph G, respectively. In t... Read More about The domination parameters of cubic graphs.