Skip to main content

Research Repository

Advanced Search

All Outputs (44)

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

Line hypergraphs (1996)
Journal Article
Zverovich, V. E., Tyshkevich, R. I., Tyshkevich, R., & Zverovich, V. (1996). Line hypergraphs. Discrete Mathematics, 161(1-3), 265-283. https://doi.org/10.1016/0012-365X%2895%2900233-M

In this paper, we introduce a new multivalued function ℒ called the line hypergraph. The function ℒ generalizes two classical concepts at once, namely, of the line graph and the dual hypergraph. In terms of this function, proofs of some known theorem... Read More about Line hypergraphs.

An induced subgraph characterization of domination perfect graphs (1995)
Journal Article
Zverovich, V. E., Zvervich, I. E., Zverovich, I., & Zverovich, V. (1995). An induced subgraph characterization of domination perfect graphs. Journal of Graph Theory, 20(3), 375-395. https://doi.org/10.1002/jgt.3190200313

Let γ(G) ι(G) be the domination number and independent domination number of a graph (G), respectively. A graph (G) is called domination perfect if γ(H) = ι(H), for every induced subgraph H of (G). There are many results giving a partial characterizat... Read More about An induced subgraph characterization of domination perfect graphs.

Disproof of a Conjecture in the Domination Theory (1994)
Journal Article
Zverovich, V. E., Zverovich, I. E., Zverovich, I., & Zverovich, V. (1994). Disproof of a Conjecture in the Domination Theory. Graphs and Combinatorics, 10(2), 389-396. https://doi.org/10.1007/BF02986690

In [1] C. Barefoot, F. Harary and K. Jones conjectured that for cubic graphs with connectivity three the difference between the domination and independent domination numbers is at most one. We disprove this conjecture and give an exhaustive answer to... Read More about Disproof of a Conjecture in the Domination Theory.

Contributions to the theory of graphic sequences (1992)
Journal Article
Zverovich, V. E., Zverovich, I. E., Zverovich, I., & Zverovich, V. (1992). Contributions to the theory of graphic sequences. Discrete Mathematics, 105(1-3), 293-303. https://doi.org/10.1016/0012-365X%2892%2990152-6

In this article we present a new version of the Erdős-Gallai theorem concerning graphicness of the degree sequences. The best conditions of all known on the reduction of the number of Erdős-Gallai inequalities are given. Moreover, we... Read More about Contributions to the theory of graphic sequences.

A characterization of domination perfect graphs (1991)
Journal Article
Zverovich, V. E., Zverovich, I. E., Zverovich, I., & Zverovich, V. (1991). A characterization of domination perfect graphs. Journal of Graph Theory, 15(2), 109-114. https://doi.org/10.1002/jgt.3190150202

Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a fini... Read More about A characterization of domination perfect graphs.