Skip to main content

Research Repository

See what's under the surface

Advanced Search

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... Read More about Basic perfect graphs and their extensions.

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... Read More about Locally well-dominated and locally independent well-dominated graphs.

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... Read More about Proof of a conjecture on irredundance perfect graphs.

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... Read More about A disproof of Henning's conjecture on irredundance perfect graphs.

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)... Read More about Perfect graphs of strong domination and independent strong domination.

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...AID-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... Read More about A semi-induced subgraph characterization of upper domination perfect graphs.

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)... Read More about Upper domination and upper irredundance perfect graphs.

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... Read More about Line hypergraphs: A survey.

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...AID-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... Read More about The Ratio of the Irredundance Number and the Domination Number for Block-Cactus Graphs.

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


;