1. On the leaves of graph search treesRobert Scheffler, 2026, izvirni znanstveni članek Opis: Graph searches and their respective search trees are widely used in algorithmic graph theory. The problem whether a given spanning tree can be a graph search tree has been considered for different searches, graph classes and search tree paradigms. Similarly, the question whether a particular vertex can be visited last by some search has been studied extensively in recent years. We combine these two problems by considering the question whether a vertex can be a leaf of a graph search tree. We show that for particular search trees, including DFS trees, this problem is easy if we allow the leaf to be the first vertex of the search ordering. We contrast this result by showing that the problem becomes hard for many searches, including DFS and BFS, if we forbid the leaf to be the first vertex. Additionally, we present several structural and algorithmic results for search tree leaves of chordal graphs.
Ključne besede: graph search, graph search trees, leaves, chordal graphs
Objavljeno v RUP: 21.12.2025; Ogledov: 170; Prenosov: 1
 Celotno besedilo (515,71 KB) |
2. |
3. |
4. Linear separation of connected dominating sets in graphsNina Chiarelli, Martin Milanič, 2019, izvirni znanstveni članek Ključne besede: connected dominating set, connected domination, connected-domishold graph, forbidden induced subgraph characterization, split graph, chordal graph, minimal cutset, minimal separator, 1-Sperner hypergraph, threshold hypergraph, threshold Boolean function, polynomial-time algorithm
Objavljeno v RUP: 04.04.2019; Ogledov: 4793; Prenosov: 167
Celotno besedilo (648,51 KB) |
5. Nove karakterizacije v strukturni teoriji grafov : 1-popolno usmerljivi grafi, produktni grafi in cena povezanostiTatiana Romina Hartinger, 2017, doktorska disertacija Ključne besede: 1-perfectly orientable graph, structural characterization of families of graphs, chordal graph, interval graph, circular arc graph, cograph, block-cactus graph, cobipartite graph, K4-minor-free graph, outerplanar graph, graph product, Cartesian product, lexicographic product, direct product, strong product, price of connectivity, cycle transversal, path transversal
Objavljeno v RUP: 09.11.2017; Ogledov: 5564; Prenosov: 44
 Povezava na celotno besedilo |
6. 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: 4747; Prenosov: 133
Celotno besedilo (300,57 KB) |
