Igor E. Zvervich
An induced subgraph characterization of domination perfect graphs
Zvervich, Igor E.; Zverovich, Vadim E.; Zverovich, Igor; Zverovich, Vadim
Authors
Abstract
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 characterization of domination perfect graphs. In this paper, we present a finite induced subgraph characterization of the entire class of domination perfect graphs. The list of forbidden subgraphs in the charcterization consists of 17 minimal domination imperfect graphs. Moreover, the dominating set and independent dominating set problems are shown to be both NP‐complete on some classes of graphs. © 1995 John Wiley & Sons, Inc. Copyright © 1995 Wiley Periodicals, Inc., A Wiley Company
Citation
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
Journal Article Type | Article |
---|---|
Publication Date | Jan 1, 1995 |
Journal | Journal of Graph Theory |
Print ISSN | 0364-9024 |
Electronic ISSN | 1097-0118 |
Publisher | Wiley |
Peer Reviewed | Peer Reviewed |
Volume | 20 |
Issue | 3 |
Pages | 375-395 |
DOI | https://doi.org/10.1002/jgt.3190200313 |
Keywords | subgraphs, domination perfect graphs |
Public URL | https://uwe-repository.worktribe.com/output/1106488 |
Publisher URL | http://dx.doi.org/10.1002/jgt.3190200313 |
You might also like
Methods of Graph Decompositions
(2022)
Book
Modern Applications of Graph Theory
(2021)
Book
The likelihood of Braess' paradox in traffic networks
(2018)
Book Chapter
Downloadable Citations
About UWE Bristol Research Repository
Administrator e-mail: repository@uwe.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search