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
On general frameworks and threshold functions for multiple domination
(2015)
Journal Article
Braess’ paradox in asymmetrical traffic networks
(2014)
Presentation / Conference Contribution
Bounds and algorithms for limited packings in graphs
(2014)
Presentation / Conference Contribution
Braess' paradox in a generalised traffic network
(2014)
Journal Article
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