Gregory Gutin
Upper domination and upper irredundance perfect graphs
Gutin, Gregory; Zverovich, Vadim
Abstract
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) = IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result. © 1998 Elsevier Science B.V. All rights reserved.
Citation
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
Journal Article Type | Article |
---|---|
Publication Date | Aug 28, 1998 |
Deposit Date | Sep 24, 2015 |
Publicly Available Date | Mar 29, 2024 |
Journal | Discrete Mathematics |
Print ISSN | 0012-365X |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 190 |
Issue | 1-3 |
Pages | 95-105 |
DOI | https://doi.org/10.1016/S0012-365X%2898%2900036-3 |
Keywords | independence number, upper domination number, upper irredundance number |
Public URL | https://uwe-repository.worktribe.com/output/1099501 |
Publisher URL | http://dx.doi.org/10.1016/S0012-365X(98)00036-3 |
Files
UpperDominationAndUpperIrredundancePerfectGraphs.pdf
(156 Kb)
PDF
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