Search the repository

On {k}-Roman graphs
Kenny Bešter Štorgel, Nina Chiarelli, Lara Fernández, J. Pascal Gollin, Claire Hilaire, Valeria Alejandra Leoni, Martin Milanič, 2025, published scientific conference contribution

Abstract: For a positive integer k, a {k}-Roman dominating function of a graph G = (V, E) is a function f : V → {0, 1, . . . , k} satisfying f (N(v)) ≥ k for each vertex v ∈ V with f (v) = 0. Every graph G satisfies γ{Rk}(G) ≤ kγ(G), where γ{Rk}(G) denotes the minimum weight of a {k}-Roman dominating function of G and γ(G) is the domination number of G. In this work we study graphs for which the equality is reached, called {k}-Roman graphs. This extends the concept of {k}-Roman trees studied by Wang et al. in 2021 to gen- eral graphs. We prove that for every k ≥ 3, the problem of recognizing {k}-Roman graphs is NP-hard, even when restricted to split graphs. We provide partial answers to the question of which split graphs are {2}-Roman: we characterize {2}-Roman split graphs that can be decomposed with respect to the split join operation into two smaller split graphs and classify the {k}-Roman property within two specific families of split graphs that are prime with respect to the split join operation: suns and their complements.
Keywords: graph domination, {k}-Roman domination, {k}-Roman graph, split graph, split join, NP-completeness
Published in RUP: 16.12.2025; Views: 201; Downloads: 2
Full text (395,09 KB)
This document has more files! More...

Allocating indivisible items with minimum dissatisfaction on preference graphs
Nina Chiarelli, Clément Jean Dallard, Andreas Darmann, Stefan Lendl, Martin Milanič, Peter Muršič, Nevena Pivač, Ulrich Pferschy, 2021, published scientific conference contribution

Keywords: fair division, partial order, preference graph
Published in RUP: 29.10.2021; Views: 3919; Downloads: 24
Link to full text

Strong cliques in diamond-free graphs
Nina Chiarelli, Berenice Martínez-Barona, Martin Milanič, Jérôme Monnot, Peter Muršič, 2020, published scientific conference contribution

Keywords: maximal clique, maximal stable set, diamond-free graph, strong clique, simplicial clique, CIS graph, NP-hard problem, linear-time algorithm, Erdős-Hajnal property
Published in RUP: 10.11.2020; Views: 3219; Downloads: 60
Link to full text

Vizingov izrek in snarki : diplomsko delo
Nina Chiarelli, 2011, undergraduate thesis

Keywords: teorija grafov, barvanje povezav grafa, kromatični indeks, Vizingov izrek, snark
Published in RUP: 23.07.2020; Views: 3300; Downloads: 80
Full text (1,44 MB)

Edge elimination schemes of weighted graph classes, Workshop on Graph Modification algorithms, experiments and new problems, 23rd - 24th January 2020, Bergen, Norway
Martin Milanič, Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, Martin Strehler, 2020, unpublished invited conference lecture

Keywords: graph class, edge elimination scheme, sandwich monotonicity
Published in RUP: 28.05.2020; Views: 3051; Downloads: 0