
handle: 20.500.12556/RUP-2624
Vizing's conjecture is true for graphs G satisfying γ i ( G ) = γ ( G ), where γ ( G ) is the domination number of a graph G and γ i ( G ) is the independence-domination number of G , that is, the maximum, over all independent sets I in G , of the minimum number of vertices needed to dominate I . The equality γ i ( G ) = γ ( G ) is known to hold for all chordal graphs and for chordless cycles of length 0 (mod 3). We prove some results related to graphs for which the above equality holds. More specifically, we show that the problems of determining whether γ i ( G ) = γ ( G ) = 2 and of verifying whether γ i ( G ) ≥ 2 are NP-complete, even if G is weakly chordal. We also initiate the study of the equality γ i = γ in the context of hereditary graph classes and exhibit two infinite families of graphs for which γ i < γ .
independence-domination number, hereditary graph class, domination number, IDD-perfect graph, Vizing's conjecture, weakly chordal graph, NP-completeness, info:eu-repo/classification/udc/519.17
independence-domination number, hereditary graph class, domination number, IDD-perfect graph, Vizing's conjecture, weakly chordal graph, NP-completeness, info:eu-repo/classification/udc/519.17
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
