Lupa

Search the repository Help

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

Options:
  Reset


1 - 10 / 10
First pagePrevious page1Next pageLast page
1.
2.
Treewidth versus clique number in graph classes with a forbidden structure
Clément Jean Dallard, Martin Milanič, Kenny Štorgel, 2020, published scientific conference contribution

Keywords: graph class, treewidth, clique number
Published in RUP: 10.11.2020; Views: 1260; Downloads: 34
URL Link to full text

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

Keywords: price of connectivity, hereditary graph class, path, cycle, transversal
Published in RUP: 08.08.2016; Views: 2802; Downloads: 121
URL Link to full text

7.
8.
Graph classes : from practice to theory
Martin Milanič, 2015, published scientific conference contribution abstract (invited lecture)

Keywords: uporaba teorije grafov, razred grafov, pragoven graf, problem nahrbtnika, application of graph theory, graph class, threshold graph, knapsack problem
Published in RUP: 08.08.2016; Views: 2359; Downloads: 15
URL Link to full text

9.
10.
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$▫.
Keywords: Vizing's conjecture, domination number, independence-domination number, weakly chordal graph, NP-completeness, hereditary graph class, IDD-perfect graph
Published in RUP: 15.10.2013; Views: 2987; Downloads: 128
.pdf Full text (300,57 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