2020/02/03 by Christina M. Mynhardt, Mynhardt, C. M., S. E. A. Ogden +1
Computer Science · Mathematics · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2002.01347
openalex publication_date 2020/02/03 · openalex created_date 2020/02/14 · openalex updated_date 2026/07/28
A total Roman dominating function on a graph G is a function f:V(G)→ \0,1,2\ such that every vertex v with f(v)=0 is adjacent to some vertex u with f(u)=2, and the subgraph of G induced by the set of all vertices w such that f(w)>0 has no isolated vertices. The weight of f is Σv∈ V(G)f(v). The total Roman domination number γtR(G) is the minimum weight of a total Roman dominating function on G. A graph G is k-γtR-edge-critical if γtR(G+e)γtR(G)=k for every edge e∈ E(G), and k-γtR-edge-removal-supercritical if it is k-γtR-edge-removal-critical and γtR(G-e)≥γtR(G)+2 for every edge e∈ E(G). A graph G is k-γtR-edge-removal-stable if γtR(G-e)=γtR(G)=k for every edge e∈ E(G). We investigate connected γtR-edge-supercritical graphs and exhibit infinite classes of such graphs. In addition, we characterize γtR-edge-removal-critical and γtR-edge-removal-supercritical graphs. Furthermore, we present a connection between k-γtR-edge-removal-supercritical and k-γtR-edge-stable graphs, and similarly between k-γtR-edge-supercritical and k-γtR-edge-removal-stable graphs.