Search

This work is related to the extension of the well-known problem of Roman domination in graph theory to fuzzy graphs. A variety of approaches have been used to explore the concept of domination in fuzzy graphs. This study uses the concept of strong domination, considering the weights of the strong edges. We introduce the strong-neighbors Roman domination number of a fuzzy graph and establish some correlations with the Roman domination in graphs. The strong-neighbors Roman domination number is determined for specific fuzzy graphs, including complete and complete bipartite fuzzy graphs. Besides, several general bounds are given. In addition, we characterize the fuzzy graphs that reach the extreme values with particular attention to fuzzy strong cycles and paths.

The concept of mutual visibility in graphs, introduced recently, addresses a fundamental problem in Graph Theory concerning the identification of the largest set of vertices in a graph such that any two vertices have a shortest path connecting them, excluding internal vertices of the set. Originally motivated by some challenges in Computer Science related to robot navigation, the problem seeks to ensure unobstructed communication channels between navigating entities. The mutual-visibility problem involves determining a largest mutual-visibility set in a graph. The mutual-visibility number of a graph represents the cardinality of the largest mutual-visibility set. This concept has sparked significant research interest, leading to connections with classical combinatorial problems like the Zarankiewicz problem and Tur\'an-type problems. In this paper, we consider practical limitations in network visibility and our investigation extends the original concept to $k$-distance mutual-visibility. In this case, a pair of vertices is considered $S$-visible if a shortest path of length at most $k$ exists, excluding internal vertices belonging to the set $S$. The $k$-distance mutual-visibility number represents the cardinality of a largest $k$-distance mutual-visibility set. We initiate the study of this new graph parameter. We prove that the associate decision problem belongs to the NP-complete class. We also give some properties and tight bounds, as well as, the exact value of such parameter for some particular non trivial graph classes.

A Roman $\{2\}$-dominating function (R2F) is a function $f:V\rightarrow \{0,1,2\}$ with the property that for every vertex $v\in V$ with $f(v)=0$ there is a neighbor $u$ of $v$ with $f(u)=2$, or there are two neighbors $x,y$ of $v$ with $f(x)=f(y)=1$. A total Roman $\{2\}$-dominating function (TR2DF) is an R2F $f$ such that the set of vertices with $f(v)>0$ induce a subgraph with no isolated vertices. The weight of a TR2DF is the sum of its function values over all vertices, and the minimum weight of a TR2DF of $G$ is the total Roman $\{2\}$-domination number $\gamma_{tR2}(G).$ In this paper, we initiate the study of total Roman $\{2\}$-dominating functions, where properties are established. Moreover, we present various bounds on the total Roman $\{2\}$-domination number. We also show that the decision problem associated with $\gamma_{tR2}(G)$ is NP-complete for bipartite and chordal graphs. {Moreover, we show that it is possible to compute this parameter in linear time for bounded clique-width graphs (including tres).}

Let $\{0,1,\dots, t\}$ be abbreviated by $[t].$ A double Roman dominating function (DRDF) on a graph $\Gamma=(V,E)$ is a map $l:V\rightarrow [3]$ satisfying \textrm{(i)} if $l(r)=0$ then there must be at least two neighbors labeled 2 under $l$ or a neighbor $r'$ with $l(r')=3$; and \textrm{(ii)} if $l(r)=1$ then $r$ must be adjacent to a vertex $r'$ such that $l(r')\geq2$. A DRDF is an outer-independent total double Roman dominating function (OITDRDF) on $\Gamma$ if the set of vertices labeled $0$ induces an edgeless subgraph and the subgraph induced by the vertices with a non-zero label has no isolated vertices. The weight of an OITDRDF is the sum of its map values over all vertices, and the outer independent total Roman dominating number $\gamma_{tdR}^{oi}(\Gamma)$ is the minimum weight of an OITDRDF on $\Gamma$. First, we prove that the problem of determining $\gamma _{tdR}^{oi}(\Gamma)$ is NP-complete for bipartite and chordal graphs, after that, we prove that it is solvable in linear time when we are restricting to bounded clique-width graphs. Moreover, we present some tight bounds on $\gamma _{tdR}^{oi}(\Gamma)$ as well as the exact values for several graph families.

A maximal double Roman dominating function (MDRDF) on a graph $G=(V,E)$ is a function $f:V(G)\rightarrow \{0,1,2,3\}$ such that \textrm{(i) }every vertex $v$ with $f(v)=0$ is adjacent to least two vertices { assigned $2$ or to at least one vertex assigned $3,$} \textrm{(ii) }every vertex $v$ with $f(v)=1$ is adjacent to at least one { vertex assigned $2$ or $3$} and \textrm{(iii) }the set $\{w\in V|~f(w)=0\}$ is not a dominating set of $G $. The weight of a MDRDF is the sum of its function values over all vertices, and the maximal double Roman domination number $\gamma _{dR}^{m}(G) $ is the minimum weight of an MDRDF on $G$. {In this paper, we initiate the study of maximal double Roman domination. We first show that the problem of determining }$\gamma _{dR}^{m}(G)$ {is NP-complete for bipartite, chordal and planar graphs. But it is solvable in linear time for bounded clique-width graphs including trees, cographs and distance-hereditary graphs. Moreover, we establish various relationships relating }$\gamma _{dR}^{m}(G)$ to some domination parameters. {For the class of trees, we show that for every tree }$T$ {of order }$n\geq 4,$ $\gamma _{dR}^{m}(T)\leq \frac{5}{4}n$ {and we characterize all trees attaining the bound. Finally, the exact values of }$\gamma _{dR}^{m}(G) $ {are given for paths and cycles.

We continue the study of restrained double Roman domination in graphs. For a graph $G=\big{(}V(G),E(G)\big{)}$, a double Roman dominating function $f$ is called a restrained double Roman dominating function (RDRD function) if the subgraph induced by $\{v\in V(G)\mid f(v)=0\}$ has no isolated vertices. The restrained double Roman domination number (RDRD number) $\gamma_{rdR}(G)$ is the minimum weight $\sum_{v\in V(G)}f(v)$ taken over all RDRD functions of $G$. We first prove that the problem of computing $\gamma_{rdR}$ is NP-hard even for planar graphs, but it is solvable in linear time when restricted to bounded clique-width graphs such as trees, cographs and distance-hereditary graphs. Relationships between $\gamma_{rdR}$ and some well-known parameters such as restrained domination number $\gamma_{r}$, domination number $\gamma$ and restrained Roman domination number $\gamma_{rR}$ are investigated in this paper by bounding $\gamma_{rdR}$ from below and above involving $\gamma_{r}$, $\gamma$ and $\gamma_{rR}$ for general graphs, respectively. We prove that $\gamma_{rdR}(T)\geq n+2$ for any tree $T\neq K_{1,n-1}$ of order $n\geq2$ and characterize the family of all trees attaining the lower bound. The characterization of graphs with small RDRD numbers is given in this paper.