Given a graph G = (V, E), a function f: V → {0, 1, 2} is a total Roman {2}-dominating function if every vertex ʋ ∈ V for which f (ʋ) = 0 satisfies that ∑u∈N (ʋ) f (ʋ) ≥ 2, where N (ʋ) repre...

Let G be a graph with no isolated vertex and $f:V\left(G\right)\to \{0,1,2\}$ a function. If f satisfies that every vertex in the set $\{v\in V(G):f(v)=0\}$ is adjacent to at least one vertex in the set $\{v\in V(G):f(v)=2\}$, and if the subgraph induced by the set $\{v\in V(G):f(v)\ge 1\}$ has no isolated vertex, then we say that f is a total Roman dominating function on G. The minimum weight $\omega \left(f\right)={\sum }_{v\in V\left(G\right)}f\left(v\right)$ among all total Roman dominating functions f on G is the total Roman domination number of G. In this article we study this parameter for the rooted product graphs. Specifically, we obtain closed formulas and tight bounds for the total Roman domination number of rooted product graphs in terms of domination invariants of the factor graphs involved in this product.

The Traveling Salesman Problem (TSP) aims to find the shortest tour for a salesman who starts and ends in the same city and visits the remaining $n-1$ cities exactly once. There are a number of common generalizations of the problem including the Multiple Traveling Salesman Problem (MTSP), where instead of one salesman, there are k salesmen and the same amount of individual tours are to be constructed. We consider the Euclidean version of the problem where the distances between the cities are calculated in two-dimensional Euclidean space. Both general the TSP and its Euclidean version are strongly NP-hard. Hence, approximation algorithms with a good practical behavior are of primary interest. We describe a general method for the solution of the Euclidean versions of the TSP (including MTSP) that yields approximation algorithms with a favorable practical behavior for large real-life instances. Our method creates special types of convex hulls, which serve as a basis for the constructions of our initial and intermediate partial solutions. Here, we overview three algorithms; one of them is for the bounded version of the MTSP. The proposed novel algorithm for the Euclidean TSP provides close-to-optimal solutions for some real-life instances.

A set $D$ of vertices of a graph $G$ is a total dominating set if every vertex of $G$ is adjacent to at least one vertex in $D$. The total dominating set $D$ is called a total co-independent dominating set if $V(G)\setminus D$ is an independent set and has at least one vertex. The minimum cardinality of any total co-independent dominating set is denoted by $\gamma_{t,coi}(G)$. In this paper, we show that, for any tree $T$ of order $n$ and diameter at least three, $n-\beta(T)\leq \gamma_{t,coi}(T)\leq n-|L(T)|$ where $\beta(T)$ is the maximum cardinality of any independent set and $L(T)$ is the set of leaves of $T$. We also characterize the families of trees attaining the extremal bounds above and show that the differences between the value of $\gamma_{t,coi}(T)$ and these bounds can be arbitrarily large for some classes of trees.

In recent years, Multimetric Indices (MMIs) have received a lot of attention thanks to their ability to develop integrative evaluations of water quality, particularly in lagoons. In this article, we propose a new MMI for determining the water quality in lagoons. The proposed index is composed of biotic and abiotic indicators, in particular macroinvertebrates, macrophytes and morphological indicators. The proposed index is based on a geometric representation of a phenomenon associated with an ecological system, the ecosystem elements are mapped as vertices of a network and the relationship between them is represented by the corresponding edges. We classify the status of water bodies, from very low to very high using the ecological quality ratio. We compare our index with different different indices that measure water quality, such as General Biotic Index ($JP\left(G\right)$), Macrophyte Index for River (MIR) and Shannon diversity index (H’) and validate our index with Pearson’s correlation coefficient. A strong correlation with the $JP\left(G\right)$ and $MIR$ indices ($R^2$ = 0.8605 and $R^2=0.7661$, respectively) is obtained. Although the proposed index is composed of other indices, the independence of the proposed index with respect to its component indices is proven and the structure of the geometric model associated to the proposed network is studied. A close relationship between the measure called medium articulation and the geometric model associated with the proposed index is highlighted, which allows to determine the missing relationships in the network using structural analysis. The proposed index presents a more comprehensive measure than most indices currently used and has the advantage in the scalability, since other existing indicators can be integrated into our model.