Academic literature on the topic 'Neighborhood total 2-domination'

Domination problems are fundamental problems in graph theory with diverse applications in optimization, network design, and computational complexity. This paper investigates {k}-domination, k-tuple domination, and their total domination variants in weighted strongly chordal graphs and chordal bipartite graphs. Specifically, the {k}-domination problem in weighted strongly chordal graphs and the total {k}-domination problem in weighted chordal bipartite graphs are shown to be solvable in O(n+m) time. For weighted proper interval graphs and convex bipartite graphs, we solve the k-tuple domination and total k-tuple domination problems in O(n2.371552log2(n)log(n/δ)), where δ is the desired accuracy. Furthermore, for weighted unit interval graphs, the k-tuple domination problem achieves a significant complexity improvement, reduced from O(nk+2) to O(n2.371552log2(n)log(n/δ)). These results are achieved through a combination of linear and integer programming techniques, complemented by totally balanced matrices, totally unimodular matrices, and graph-specific matrix representations such as neighborhood and closed neighborhood matrices.

Let G = (V (G), E(G)) be an undirected graph with γ(C) ̸= 1 for each component C of G. Let S = (v1, v2, · · · , vk) be a sequence of distint vertices of a graph G, and let Sˆ ={v1, v2, . . . , vk}. Then S is a legal open hop neighborhood sequence if N2G(vi) \Si−1j=1 N2G(vj ) ̸= ∅for every i ∈ {2, . . . , k}. If, in addition, Sˆ is a total hop dominating set of G, then S is a Grundy total hop dominating sequence. The maximum length of a Grundy total hop dominating sequence in a graph G, denoted by γth gr(G), is the Grundy total hop domination number of G. In this paper, we show that the Grundy total hop domination number of a graph G is between the total hop domination number and twice the Grundy hop domination number of G. Moreover, determine values or bounds of the Grundy total hop domination number of some graphs.

The graph G = (V,E) we mean a finite, undirected graph with neither loops nor multiple edges. The order and size of G are denoted by n and m respectively. For graph theoretic terminology we refer to Chartrand and Lesniak [3] and Haynes et.al [5-6].

A total Roman $\{2\}$-dominating function (TR2DF) on a graph $G$ with vertex set $V$ is a function $f: V\rightarrow \{0,1,2\}$ having the property that for every vertex $v$ with $f(v)=0$, $\sum_{u\in N(v)}f(u)\geq 2$, where $N(v)$ represents the open neighborhood of $v$, and the subgraph of $G$ induced by the set of vertices with $f(v)>0$ has no isolated vertex. The weight of a TR2DF $f$ is the value $w(f)=\sum_{v\in V} f(v)$, and the minimum weight of a TR2DF of $G$ is the total Roman $\{2\}$-domination number $\gamma_{tR2}(G)$. The total Roman $\{2\}$-domination problem (TR2DP) is to determine the value $\gamma_{tR2}(G)$. In this paper, we first propose an integer linear programming (ILP) formulation for the TR2DP. Furthermore, we apply the discharging approach to determine the total Roman $\{2\}$-domination number for some Cartesian products of paths and cycles.

Let $G=(V,E)$ be a finite and simple graph of order $n$ and maximumdegree $\Delta$. A signed strong total Roman dominating function ona graph $G$ is a function $f:V(G)\rightarrow\{-1, 1,2,\ldots, \lceil\frac{\Delta}{2}\rceil+1\}$ satisfying the condition that (i) forevery vertex $v$ of $G$, $f(N(v))=\sum_{u\in N(v)}f(u)\geq 1$, where$N(v)$ is the open neighborhood of $v$ and (ii) every vertex $v$ forwhich $f(v)=-1$ is adjacent to at least one vertex$w$ for which $f(w)\geq 1+\lceil\frac{1}{2}\vert N(w)\cap V_{-1}\vert\rceil$, where$V_{-1}=\{v\in V: f(v)=-1\}$.The minimum of thevalues $\omega(f)=\sum_{v\in V}f(v)$, taken over all signed strongtotal Roman dominating functions $f$ of $G$, is called the signed strong totalRoman domination number of $G$ and is denoted by $\gamma_{ssTR}(G)$.In this paper, we initiate signed strong total Roman domination number of a graph and giveseveral bounds for this parameter. Then, among other results, we determine the signed strong total Roman dominationnumber of special classes of graphs.

A total dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex of $G$ has a neighbor in $D$. A locating-total dominating set of $G$ is a total dominating set $D$ of $G$ with the additional property that every two distinct vertices outside $D$ have distinct neighbors in $D$; that is, for distinct vertices $u$ and $v$ outside $D$, $N(u) \cap D \ne N(v) \cap D$ where $N(u)$ denotes the open neighborhood of $u$. A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-total domination number of $G$, denoted $\gamma_t^L(G)$, is the minimum cardinality of a locating-total dominating set in $G$. It is well-known that every connected graph of order $n \ge 3$ has a total dominating set of size at most $\frac{2}{3}n$. We conjecture that if $G$ is a twin-free graph of order $n$ with no isolated vertex, then $\gamma_t^L(G) \le \frac{2}{3}n$. We prove the conjecture for graphs without $4$-cycles as a subgraph. We also prove that if $G$ is a twin-free graph of order $n$, then $\gamma_t^L(G) \le \frac{3}{4}n$.