Lutz Volkmann
A disproof of Henning's conjecture on irredundance perfect graphs
Volkmann, Lutz; Zverovich, Vadim
Abstract
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 Henning (Chartrand and Lesniak, Graphs & Digraphs, 3rd Edition, Chapman & Hall, London, 1996, p. 321; Henning, Discrete Math. 142 (1995) 107) that a graph G is irredundance perfect if and only if ir(H) = γ(H) for every induced subgraph H of G with ir(H) ≤ 4. We also give a summary of known results on irredundance perfect graphs. Moreover, the irredundant set problem and the dominating set problem are shown to be NP-complete on some classes of graphs. A number of problems and conjectures are proposed. © 2002 Elsevier Science B.V. All rights reserved.
Journal Article Type | Article |
---|---|
Publication Date | Jun 10, 2002 |
Journal | Discrete Mathematics |
Print ISSN | 0012-365X |
Publisher | Elsevier |
Peer Reviewed | Not Peer Reviewed |
Volume | 254 |
Issue | 1-3 |
Pages | 539-554 |
DOI | https://doi.org/10.1016/S0012-365X%2801%2900300-4 |
Keywords | mathematics, maths, graphs, Henning, irredundance |
Public URL | https://uwe-repository.worktribe.com/output/1077756 |
Publisher URL | http://dx.doi.org/10.1016/S0012-365X(01)00300-4 |
You might also like
Methods of Graph Decompositions
(2024)
Book
Modern Applications of Graph Theory
(2021)
Book
The likelihood of Braess' paradox in traffic networks
(2018)
Book Chapter
Extending indoor open street mapping environments to navigable 3D citygml building models: Emergency response assessment
(2018)
Presentation / Conference Contribution
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 © 2025
Advanced Search