Lupa

Search the repository Help

A- | A+ | Print
Query: search in
search in
search in
search in
* old and bolonia study programme

Options:
  Reset


1 - 7 / 7
First pagePrevious page1Next pageLast page
1.
A note on domination and independence-domination numbers of graphs
Martin 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 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$▫.
Found in: ključnih besedah
Summary of found: ...▫$\gamma^i = \gamma$▫ in the context of hereditary graph classes and exhibit two infinite families... ...number, weakly chordal graph, NP-completeness, hereditary graph class, IDD-perfect graph...
Keywords: Vizing's conjecture, domination number, independence-domination number, weakly chordal graph, NP-completeness, hereditary graph class, IDD-perfect graph
Published: 15.10.2013; Views: 1304; Downloads: 70
URL Full text (0,00 KB)

2.
Graphs of separability at most 2
Ferdinando Cicalese, Martin Milanič, 2012, published scientific conference contribution

Found in: ključnih besedah
Summary of found: ...separability, hereditary class, separating clique, decomposition, induced subgraph, induced...
Keywords: separability, hereditary class, separating clique, decomposition, induced subgraph, induced minor, parsimony haplotyping
Published: 15.10.2013; Views: 1034; Downloads: 51
URL Full text (0,00 KB)

3.
Linear separation of connected dominating sets in graphs
Martin Milanič, Nina Chiarelli, 2014, published scientific conference contribution

Found in: ključnih besedah
Summary of found: ...Spernerjev hipergraf, pragovni hipergraf, connected dominating set, hereditary graph class, dually Sperner hypergraph, treshold hypergraph,...
Keywords: povezana dominantna množica, hereditarni grafovski razred, dualno Spernerjev hipergraf, pragovni hipergraf, connected dominating set, hereditary graph class, dually Sperner hypergraph, treshold hypergraph
Published: 15.10.2015; Views: 1274; Downloads: 48
URL Full text (0,00 KB)

4.
Graph classes with and without powers of bounded clique-width
Martin Milanič, Flavia Bonomo, Luciano Grippo, Martin Dario Safe, 2016, original scientific article

Found in: ključnih besedah
Summary of found: ...clique-width, power of a graph, hereditary graph class, power-bounded clique-width, ...
Keywords: clique-width, power of a graph, hereditary graph class, power-bounded clique-width
Published: 03.04.2017; Views: 657; Downloads: 93
URL Full text (0,00 KB)

5.
The price of connectivity for cycle transversals
Tatiana R. Hartinger, Matthew Johnson, Martin Milanič, Daniël Paulusma, 2015, published scientific conference contribution

Found in: ključnih besedah
Summary of found: ...price of connectivity, hereditary graph class, path, cycle, transversal, ...
Keywords: price of connectivity, hereditary graph class, path, cycle, transversal
Published: 08.08.2016; Views: 1410; Downloads: 47
URL Full text (0,00 KB)

6.
The price of connectivity for cycle transversals
Tatiana R. Hartinger, Matthew Johnson, Martin Milanič, Daniël Paulusma, 2016, original scientific article

Found in: ključnih besedah
Summary of found: ...price of connectivity, hereditary graph class, path, cycle, transversal, ...
Keywords: price of connectivity, hereditary graph class, path, cycle, transversal
Published: 08.08.2016; Views: 870; Downloads: 43
URL Full text (0,00 KB)

7.
Minimal separators in graph classes defined by small forbidden induced subgraphs
Martin Milanič, Nevena Mitrović, 2019, published scientific conference contribution

Found in: ključnih besedah
Summary of found: ...minimal separator, hereditary graph class, forbidden induced subgraph...
Keywords: minimal separator, hereditary graph class, forbidden induced subgraph
Published: 16.10.2019; Views: 110; Downloads: 41
URL Full text (0,00 KB)

Search done in 0 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica