Search

A double Roman dominating function of a graph G is a labeling f : V ( G ) → {0, 1, 2, 3} such that if f ( v ) = 0 , then the vertex v must have at least two neighbors labeled 2 under f or one neighbor with f ( w ) = 3 , and if f ( v ) = 1 , then v must have at least one neighbor with f ( w ) ≥ 2. The double Roman domination number γ dR ( G ) of G is the minimum value of Σ v  ∈  V ( G ) f ( v ) over such functions. In this paper, we firstly give some bounds of the double Roman domination numbers of graphs with given minimum degree and graphs of diameter 2, and further we get that the double Roman domination numbers of almost all graphs are at most n . Then we obtain sharp upper and lower bounds for γ d R ( G ) + γ d R ( G ¯ ) . Moreover, a linear time algorithm for the double Roman domination number of a cograph is given and a characterization of the double Roman cographs is provided. Those results partially answer two open problems posed by Beeler et al. (2016). [ABSTRACT FROM AUTHOR]

The entropy of a graph is an information-theoretic quantity for measuring the complexity of a graph. After Shannon introduced the entropy to information and communication, many generalizations of the entropy measure have been proposed, such as Rényi entropy and Daróczy entropy. In this article, we prove accurate connections (inequalities) between generalized graph entropies, graph energies, and topological indices. Additionally, we obtain some extremal properties of nine generalized graph entropies by employing graph energies and topological indices. [ABSTRACT FROM AUTHOR]

In the work, we prove that γ t (F) ≤ a (F) + 1 holds for a tree-like graph F , where γ t (F) and a (F) denote the total domination number and annihilation number of a connected graph F , respectively. This result generalizes some results of Desormeaux et al. (2013) and Bujtás and Jakovac (2019). [ABSTRACT FROM AUTHOR]