Search

Given a graph G = (V , E) , the Perfect Italian domination function is a mapping f : V → { 0 , 1 , 2 } such that for any vertex v ∈ V with f(v) equals zero, ∑ u ∈ N (v) f (u) must be two. In simpler terms, for each vertex v labeled zero, one of the following conditions must be satisfied: (1) exactly two neighbours of v are labeled 1, and every other neighbour of v is labeled zero, (2) exactly one neighbour of v is labeled 2, and every other neighbour of v is labeled zero. The weight of the function f is calculated as the sum of f(u) over all u ∈ V . The Perfect Italian domination problem involves finding a Perfect Italian domination function that minimizes the weight. We have devised a linear-time algorithm to solve this problem for P 4 -sparse graphs, which represent well-established generalization of cographs. Furthermore, we have proved that the problem is efficiently solvable for distance-hereditary graphs. We have also shown that the decision version of the problem is NP-complete for 5-regular graphs and comb convex bipartite graphs. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph with no isolated vertices. A vertex v totally dominates a vertex w ( w ≠ v ), if v is adjacent to w. A set D ⊆ V called a total dominating set of G if every vertex v ∈ V is totally dominated by some vertex in D. The minimum cardinality of a total dominating set is the total domination number of G and is denoted by γ t (G) . A total dominator coloring of graph G is a proper coloring of vertices of G, so that each vertex totally dominates some color class. The total dominator chromatic number χ td (G) of G is the least number of colors required for a total dominator coloring of G. The Total Dominator Coloring problem is to find a total dominator coloring of G using the minimum number of colors. It is known that the decision version of this problem is NP-complete for general graphs. We show that it remains NP-complete even when restricted to bipartite, planar and split graphs. We further study the Total Dominator Coloring problem for various graph classes, including trees, cographs and chain graphs. First, we characterize the trees having χ td (T) = γ t (T) + 1 , which completes the characterization of trees achieving all possible values of χ td (T) . Also, we show that for a cograph G, χ td (G) can be computed in linear-time. Moreover, we show that 2 ≤ χ td (G) ≤ 4 for a chain graph G and then we characterize the class of chain graphs for every possible value of χ td (G) in linear-time. [ABSTRACT FROM AUTHOR]