1. Conformality of minimal transversals of maximal cliquesEndre Boros, Vladimir Gurvich, Martin Milanič, Dmitry Tikhanovsky, Yushi Uno, 2026, original scientific article Abstract: Given a hypergraph ℋ, the dual hypergraph of ℋis the hypergraph of all minimal transversals of ℋ. A hypergraph is conformal if it is the family of maximal cliques of a graph. In a recent work, Boros, Gurvich, Milanič, and Uno (Journal of Graph Theory, 2025) studied conformality of dual hypergraphs and proved several results related to this property, leading in particular to a polynomial-time algorithm for recognizing graphs in which, for any fixed k, all minimal transversals of maximal cliques have size at most k. In this follow-up work, we provide a novel aspect to the study of graph clique transversals, by considering the dual conformality property from the perspective of graphs. More precisely, we study graphs for which the family of minimal transversals of maximal cliques is conformal. Such graphs are called clique dually conformal (CDC for short). It turns out that the class of CDC graphs is a rich generalization of the class of P4-free graphs. As our main results, we completely completely characterize CDC graphs within the families of triangle-free graphs and split graphs. Both characterizations lead to polynomial-time recognition algorithms. Generalizing the fact that every P4-free graph is CDC, we also show that the class of CDC graphs is closed under substitution, in the strong sense that substituting a graph H for a vertex of a graph G results in a CDC graph if and only if both G and H are CDC.
Keywords: maximal clique, minimal transversal, conformal hypergraph, triangle-free graph, split graph
Published in RUP: 16.12.2025; Views: 197; Downloads: 2
 Full text (1,65 MB)
This document has more files! More... |
2. On {k}-Roman graphsKenny 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... |
3. On the proper interval completion problem within some chordal subclassesFrançois Dross, Claire Hilaire, Ivo Koch, Valeria Alejandra Leoni, Nina Pardal, María Inés Lopez Pujato, Vinicius Fernandes dos Santos, 2025, original scientific article Abstract: Given a property (graph class) Π, a graph G, and an integer k, the Π-completion problem consists of deciding whether we can turn G into a graph with the property Π by adding at most k edges to G. The Π-completion problem is known to be NP-hard for general graphs when Π is the property of being a proper interval graph (PIG). In this work, we study the PIG-completion problem within different subclasses of chordal graphs. We show that the problem remains NP-complete even when restricted to split graphs. We then turn our attention to positive results and present polynomial time algorithms to solve the PIG-completion problem when the input is restricted to caterpillar and threshold graphs. We also present an efficient algorithm for the minimum co-bipartite-completion for quasi-threshold graphs, which provides a lower bound for the PIG-completion problem within this graph class.
Keywords: proper interval completion, split graph, threshold graph, quasi-threshold graph, caterpillar
Published in RUP: 06.08.2025; Views: 420; Downloads: 9
Full text (824,75 KB)
This document has more files! More... |
4. Edge elimination and weighted graph classesJesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Matjaž Krnc, Martin Milanič, Nevena Pivač, Robert Scheffler, Martin Strehler, 2020, published scientific conference contribution Keywords: edge elimination, weighted graph, split graph, threshold graph, chain graph, linear-time recognition algorithm
Published in RUP: 10.11.2020; Views: 3044; Downloads: 38
 Link to full text |
5. Linear separation of connected dominating sets in graphsNina Chiarelli, Martin Milanič, 2019, original scientific article Keywords: 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
Published in RUP: 04.04.2019; Views: 4795; Downloads: 167
Full text (648,51 KB) |
6. On split liftings with sectional complementsAleksander Malnič, Rok Požar, 2018, original scientific article Keywords: algorithm, Cayley voltages, covering projection, graph, group presentation, invariant section, lifting automorphisms, linear systems over the integers, split extension
Published in RUP: 02.03.2018; Views: 4906; Downloads: 181
Link to full text |
7. |
8. |
9. |
10. Connected graphs of fixed order and size with minimal index : structural considerationsSlobodan Simić, Enzo M. Li Marzi, Francesco Belardo, 2004, original scientific article Keywords: spekter grafa, največja lastna vrednost, spektralni radij, indeks grafa, graph spectrum, largest eingenvalue, spectral radius, graph index, nested split graphs
Published in RUP: 15.10.2015; Views: 5026; Downloads: 63
Link to full text |
