1. Strong cliques in diamond-free graphsNina Chiarelli, Berenice Martínez-Barona, Martin Milanič, Jérôme Monnot, Peter Muršič, 2020, izvirni znanstveni članek Ključne besede: maximal clique, maximal stable set, diamond-free graph, strong clique, simplicial clique, strongly perfect graph, CIS graph, NP-hard problem, polynomial-time algorithm, Erdős-Hajnal property
Objavljeno v RUP: 17.12.2020; Ogledov: 1311; Prenosov: 42
 Povezava na celotno besedilo |
2. |
3. Reconstructing perfect phylogenies via binary matrices, branchings in DAGs, and a generalization of Dilworth's theoremMartin Milanič, 2018, objavljeni povzetek znanstvenega prispevka na konferenci (vabljeno predavanje) Ključne besede: perfect phylogeny, NP-hard problem, graph coloring, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Objavljeno v RUP: 17.09.2018; Ogledov: 1925; Prenosov: 20
Povezava na celotno besedilo |
4. On cyclic edge-connectivity of fullerenesKlavdija Kutnar, Dragan Marušič, 2008, izvirni znanstveni članek Opis: A graph is said to be cyclically ▫$k$▫-edge-connected, if at least ▫$k$▫ edges must be removed to disconnect it into two components, each containing a cycle. Such a set of ▫$k$▫ edges is called a cyclic-k-edge cutset and it is called a trivial cyclic-k-edge cutset if at least one of the resulting two components induces a single ▫$k$▫-cycle. It is known that fullerenes, that is, 3-connected cubic planar graphs all of whose faces are pentagons and hexagons, are cyclically 5-edge-connected. In this article it is shown that a fullerene ▫$F$▫ containing a nontrivial cyclic-5-edge cutset admits two antipodal pentacaps, that is, two antipodal pentagonal faces whose neighboring faces are also pentagonal. Moreover, it is shown that ▫$F$▫ has a Hamilton cycle, and as a consequence at least ▫$15 \cdot 2^{n/20-1/2}$▫ perfect matchings, where ▫$n$▫ is the order of ▫$F$▫.
Ključne besede: graph, fullerene graph, cyclic edge-connectivity, hamilton cycle, perfect matching
Objavljeno v RUP: 03.04.2017; Ogledov: 2152; Prenosov: 138
Povezava na celotno besedilo |
5. |
6. On hereditary efficiently dominatable graphsMartin Milanič, 2011, objavljeni povzetek znanstvenega prispevka na konferenci Ključne besede: popolna koda, učinkovita dominacija, grafi z učinkovito dominantno množico, polinomski algoritmi, hereditarni grafovski razredi, perfect code, efficient domination, efficiently dominatable graphs, polynomial time algorithms, hereditary graph classes
Objavljeno v RUP: 15.10.2015; Ogledov: 3447; Prenosov: 245
Povezava na celotno besedilo |
7. A note on domination and independence-domination numbers of graphsMartin Milanič, 2013, objavljeni znanstveni prispevek na konferenci Opis: 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$▫.
Ključne besede: Vizing's conjecture, domination number, independence-domination number, weakly chordal graph, NP-completeness, hereditary graph class, IDD-perfect graph
Objavljeno v RUP: 15.10.2013; Ogledov: 3109; Prenosov: 128
 Celotno besedilo (300,57 KB) |
8. |
