1. A note on domination and independencedomination numbers of graphsMartin Milanič, 2013, published scientific conference contribution Abstract: 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 independencedomination 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 NPcomplete, 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$▫. Found in: ključnih besedah Summary of found: ...\gamma(G)$▫ is known to hold for all chordal graphs and for chordless cycles of length... Keywords: Vizing's conjecture, domination number, independencedomination number, weakly chordal graph, NPcompleteness, hereditary graph class, IDDperfect graph Published: 15.10.2013; Views: 2400; Downloads: 122 This document has more files! More...

2. Nove karakterizacije v strukturni teoriji grafovTatiana Romina Hartinger, 2017, doctoral dissertation Found in: ključnih besedah Summary of found: ...graph, structural characterization of families of graphs, chordal graph, interval graph, circular arc graph, cograph,... Keywords: 1perfectly orientable graph, structural characterization of families of graphs, chordal graph, interval graph, circular arc graph, cograph, blockcactus graph, cobipartite graph, K4minorfree graph, outerplanar graph, graph product, Cartesian product, lexicographic product, direct product, strong product, price of connectivity, cycle transversal, path transversal Published: 09.11.2017; Views: 1733; Downloads: 29 Full text (0,00 KB) 
3. Linear separation of connected dominating sets in graphsMartin Milanič, Nina Chiarelli, 2019, original scientific article Found in: ključnih besedah Summary of found: ...graph, forbidden induced subgraph characterization, split graph, chordal graph, minimal cutset, minimal separator, 1Sperner hypergraph,... Keywords: connected dominating set, connected domination, connecteddomishold graph, forbidden induced subgraph characterization, split graph, chordal graph, minimal cutset, minimal separator, 1Sperner hypergraph, threshold hypergraph, threshold Boolean function, polynomialtime algorithm Published: 04.04.2019; Views: 1287; Downloads: 156 This document has more files! More...

4. Detecting strong cliquesMartin Milanič, Bernard Ries, Ademir Hujdurović, 2019, original scientific article Found in: ključnih besedah Summary of found: ...strong clique, weakly chordal graph, line graph, cubic graph... Keywords: strong clique, weakly chordal graph, line graph, cubic graph Published: 30.06.2019; Views: 1544; Downloads: 200 Full text (0,00 KB) 