Search the repository

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: 425; Downloads: 3
Full text (395,09 KB)
This document has more files! More...

Abstract: Distance energy of a graph is a recent energy-type invariant, defined as the absolute deviation of the eigenvalues of the distance matrix of the graph. Two graphs of the same order are said to be distance equienergetic if they have equal distance energy, while they have distinct spectra of their distance matrices. Examples of pairs of distance equienergetic graphs appear in the literature already, but most of them have diameter two only. We describe here the distance spectrum of a special composition of regular graphs, and, as an application, we show that for any ▫$n \ge 3$▫, there exists a set of ▫$n + 1$▫ distance equienergetic graphs which have order ▫$6n$▫ and diameter ▫$n - 1$▫ each.
Keywords: graph theory, distance spectrum, distance energy, join, regular graphs
Published in RUP: 15.10.2013; Views: 7179; Downloads: 152
Full text (144,63 KB)