Research Repository

# Browse

Basic perfect graphs and their extensions (2005)
Journal Article
Zverovich, V. E., Zverovich, I. E., & Zverovich, V. (2005). Basic perfect graphs and their extensions. Discrete Mathematics, 293(1-3), 291-311. https://doi.org/10.1016/j.disc.2004.08.033

In this article, we present a characterization of basic graphs in terms of forbidden induced subgraphs. This class of graphs was introduced by Conforti et al. (Square-free perfect graphs, J. Combin. Theory Ser. B, 90 (2) (2004) 257-307), and it plays...

Basic graphs (2003)
Presentation / Conference
Zverovich, V., & Zverovich, I. (2003, June). Basic graphs. Paper presented at The 19th British Combinatorial Conference

Locally well-dominated and locally independent well-dominated graphs (2003)
Journal Article
Zverovich, I., & Zverovich, V. (2003). Locally well-dominated and locally independent well-dominated graphs. Graphs and Combinatorics, 19(2), 279-288. https://doi.org/10.1007/s00373-002-0507-7

In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs, and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irred...

Proof of a conjecture on irredundance perfect graphs (2002)
Journal Article
Volkmann, L., & Zverovich, V. (2002). Proof of a conjecture on irredundance perfect graphs. Journal of Graph Theory, 41(4), 292-306. https://doi.org/10.1002/jgt.10068

Let ir(G) and γ(G) be the irredundance number and the domination number of a graph G, respectively. A graph G is called irredundance perfect if ir(H) = γ(H), for every induced subgraph H of G. In this article we present a result which immediately imp...

A disproof of Henning's conjecture on irredundance perfect graphs (2002)
Journal Article
Volkmann, L., & Zverovich, V. (2002). A disproof of Henning's conjecture on irredundance perfect graphs. Discrete Mathematics, 254(1-3), 539-554. https://doi.org/10.1016/S0012-365X%2801%2900300-4

Let ir(G) and γ(G) be the irredundance number and the domination number of a graph G, respectively. A graph G is called irredundance perfect if ir(H) = γ(H), for every induced subgraph H of G. In this paper, we disprove the known conjecture of Hennin...

Perfect graphs of strong domination and independent strong domination (2001)
Journal Article
Zverovich, V. E., Rautenbach, D., & Zverovich, V. (2001). Perfect graphs of strong domination and independent strong domination. Discrete Mathematics, 226(1-3), 297-311. https://doi.org/10.1016/S0012-365X%2800%2900116-3

Let γ(G), i(G), γs(G) and is(G) denote the domination number, the independent domination number, the strong domination number and the independent strong domination number of a graph G, respectively. A graph G is called γi-perfect (domination perfect)...

A semi-induced subgraph characterization of upper domination perfect graphs (1999)
Journal Article
Zverovich, V. E., Zverovich, I. E., Zverovich, I., & Zverovich, V. (1999). A semi-induced subgraph characterization of upper domination perfect graphs. Journal of Graph Theory, 31(1), 29-49. https://doi.org/10.1002/%28SICI%291097-0118%28199905%2931%3A1%3C29%3A%3AAID-JGT4%3E3.0.CO%3B2-G

Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classe...

Upper domination and upper irredundance perfect graphs (1998)
Journal Article
Gutin, G., & Zverovich, V. (1998). Upper domination and upper irredundance perfect graphs. Discrete Mathematics, 190(1-3), 95-105. https://doi.org/10.1016/S0012-365X%2898%2900036-3

Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H)...

Line hypergraphs: A survey (1998)
Journal Article
Tyshkevich, R., & Zverovich, V. (1998). Line hypergraphs: A survey. Acta Applicandae Mathematicae, 52(1), 209-222. https://doi.org/10.1023/A%3A1005963110362

The survey is devoted to line graphs and a new multivalued function L called the line hypergraph. This function generalizes two classical concepts at once, namely the line graph and the dual hypergraph. In a certain sense, line graphs and dual hyperg...

The Ratio of the Irredundance Number and the Domination Number for Block-Cactus Graphs (1998)
Journal Article
Zverovich, V. (1998). The Ratio of the Irredundance Number and the Domination Number for Block-Cactus Graphs. Journal of Graph Theory, 29(3), 139-149. https://doi.org/10.1002/%28SICI%291097-0118%28199811%2929%3A3%3C139%3A%3AAID-JGT2%3E3.0.CO%3B2-R

Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43-56] and Bollobás and Cockayne [J. Graph Theory (1979) 241-2...

Pi-tau-perfect graphs (1997)
Presentation / Conference
Zverovich, V. (1997, October). Pi-tau-perfect graphs. Presented at Mathematical Colloquium