0 KB300 KB24 KB200820252013Milanič, Martinštevilka:1letnik:6str. 89-97COBISSID:1024423764ISSN:1855-3966URN:URN:NBN:SI:doc-5EXVXLEWenDruštvo matematikov, fizikov in astronomov SlovenijeArs mathematica contemporaneadomination numberhereditary graph classIDD-perfect graphindependence-domination numberNP-completenessVizing's conjectureweakly chordal graphA note on domination and independence-domination numbers of graphs|Vizing's conjecture is true for graphs ?$G$? satisfying ?$\gamma^i(G) = \gamma(G)$?, where ?$\gamma(G)$? is the domination number of a graph ?$G$? and ?$\gamma^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 ?$\gamma^i(G) = \gamma(G)$? is known to hold for all chordal graphs and for chordless cycles of length ?$0 \pmod{3}$?. We prove some results related to graphs for which the above equality holds. More specifically, we show that the problems of determining whether ?$\gamma^i(G) = \gamma(G) = 2$? and of verifying whether ?$\gamma^i(G) \ge 2$? are NP-complete, even if ?$G$? is weakly chordal. We also initiate the study of the equality ?$\gamma^i = \gamma$? in the context of hereditary graph classes and exhibit two infinite families of graphs for which ?$\gamma^i < \gamma$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije