Hexagonal chains are a special class of data condensed benzenoid system and phenylene chains are a class of polycyclic aromatic compounds. In this paper, we determine the expected values of the Hyper ...Zagreb and forgotten topological indices for this class of conjugated hydrocarbons. The comparisons between the expected values of these indices concerning the random phenylene chains have been determined explicitly. The graphical illustrations have been given in terms of the differences between the expected values of these indices.
If $G$ is a graph with vertex set $V(G)$, then let $Nu$ be the closed neighborhood of the vertex $u\in V(G)$. A total double Italian dominating function (TDIDF) on a graph $G$ is a function ...$f:V(G)\rightarrow\{0,1,2,3\}$ satisfying (i) $f(Nu)\ge 3$ for every vertex $u\in V(G)$ with $f(u)\in\{0,1\}$ and (ii) the subgraph induced by the vertices with a non-zero label has no isolated vertices. A TDIDF is an outer-independent total double Italian dominating function (OITDIDF) on $G$ if the set of vertices labeled $0$ induces an edgeless subgraph. The weight of an OITDIDF is the sum of its function values over all vertices, and the outer independent total double Italian domination number $\gamma_{tdI}^{oi}(G)$ is the minimum weight of an OITDIDF on $G$. In this paper, we establish various bounds on $\gamma_{tdI}^{oi}(G)$, and we determine this parameter for some special classes of graphs.
Let
G
be a graph with vertex set
V
(
G
). A total Italian dominating function (TIDF) on a graph
G
is a function
f
:
V
(
G
) → {0, 1, 2} such that (i) every vertex
v
with
f
(
v
) = 0 is adjacent to ...a vertex
u
with
f
(
u
) = 2 or to two vertices
w
and
z
with
f
(
w
) =
f
(
z
) = 1, and (ii) every vertex
v
with
f
(
v
) ≥ 1 is adjacent to a vertex
u
with
f
(
u
) ≥ 1. The total Italian domination number
γ
tI
(
G
) on a graph
G
is the minimum weight of a total Italian dominating function. In this paper, we present Nordhaus–Gaddum type inequalities for the total Italian domination number.
Total Italian domatic number of graphs Sheikholeslami, Seyed Mahmoud; Volkmann, Lutz
Computer science journal of Moldova,
07/2023, Volume:
31, Issue:
2 (92)
Journal Article
Peer reviewed
Open access
Let $G$ be a graph with vertex set $V(G)$. An \textit{Italian dominating function} (IDF) on a graph $G$ is a function $f:V(G)\longrightarrow \{0,1,2\}$ such that every vertex $v$ with $f(v)=0$ is ...adjacent to a vertex $u$ with $f(u)=2$ or to two vertices $w$ and $z$ with $f(w)=f(z)=1$. An IDF $f$ is called a \textit{total Italian dominating function} if every vertex $v$ with $f(v)\ge 1$ is adjacent to a vertex $u$ with $f(u)\ge 1$. A set $\{f_1,f_2,\ldots,f_d\}$ of distinct total Italian dominating functions on $G$ with the property that $\sum_{i=1}^df_i(v)\le 2$ for each vertex $v\in V(G)$, is called a \textit{total Italian dominating family} (of functions) on $G$. The maximum number of functions in a total Italian dominating family on $G$ is the \textit{total Italian domatic number} of $G$, denoted by $d_{tI}(G)$. In this paper, we initiate the study of the total Italian domatic number and present different sharp bounds on $d_{tI}(G)$. In addition, we determine this parameter for some classes of graphs.
A restrained {2}-dominating function (R{2}DF) on a graph
G
= (
V
,
E
) is a function
f
:
V
→ {0, 1, 2} such that : (i)
f
(
N
v
) ≥ 2 for all
v
∈
V
, where
N
v
is the set containing
v
and all ...vertices adjacent to
v
; (ii) the subgraph induced by the vertices assigned 0 under
f
has no isolated vertices. The weight of an R{2}DF is the sum of its function values over all vertices, and the restrained {2}-domination number
γ
r
{2}(
G
) is the minimum weight of an R{2}DF on
G
. In this paper, we initiate the study of the restrained {2}-domination number. We first prove that the problem of computing this parameter is NP-complete, even when restricted to bipartite graphs. Then we give various bounds on this parameter. In particular, we establish upper and lower bounds on the restrained {2}-domination number of a tree
T
in terms of the order, the numbers of leaves and support vertices.
An independent Roman dominating function (IRD-function) on a graph
G
is a function
f
:
V
(
G
) → {0, 1, 2} satisfying the conditions that (i) every vertex
u
for which
f
(
u
) = 0 is adjacent to at ...least one vertex
v
for which
f
(
v
) = 2, and (ii) the set of all vertices assigned non-zero values under
f
is independent. The weight of an IRD-function is the sum of its function values over all vertices, and the independent Roman domination number
i
R
(
G
) of
G
is the minimum weight of an IRD-function on
G
. In this paper, we initiate the study of the independent Roman bondage number
b
iR
(
G
) of a graph
G
having at least one component of order at least three, defined as the smallest size of set of edges
F
⊆
E
(
G
) for which
i
R
(
G
−
F
) >
i
R
(
G
). We begin by showing that the decision problem associated with the independent Roman bondage problem is NP-hard for bipartite graphs. Then various upper bounds on
b
iR
(
G
) are established as well as exact values on it for some special graphs. In particular, for trees
T
of order at least three, it is shown that
b
iR
(
T
) ≤ 3, while for connected planar graphs the upper bounds are in terms of the maximum degree with refinements depending on the girth of the graph.
Let <inline-formula> <tex-math notation="LaTeX">G=(V,E) </tex-math></inline-formula> be a simple graph. A double Roman dominating function (DRDF) on <inline-formula> <tex-math notation="LaTeX">G ...</tex-math></inline-formula> is a function <inline-formula> <tex-math notation="LaTeX">f </tex-math></inline-formula> from the vertex set <inline-formula> <tex-math notation="LaTeX">V </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula> into <inline-formula> <tex-math notation="LaTeX">\{0,1,2,3\} </tex-math></inline-formula> such that if <inline-formula> <tex-math notation="LaTeX">f(u)=0 </tex-math></inline-formula>, then <inline-formula> <tex-math notation="LaTeX">u </tex-math></inline-formula> must have at least two neighbors assigned 2 or one neighbor assigned 3 under <inline-formula> <tex-math notation="LaTeX">f </tex-math></inline-formula>, and if <inline-formula> <tex-math notation="LaTeX">f(u)=1 </tex-math></inline-formula>, then <inline-formula> <tex-math notation="LaTeX">u </tex-math></inline-formula> must have at least one neighbor assigned at least 2 under <inline-formula> <tex-math notation="LaTeX">f </tex-math></inline-formula>. The weight of a DRDF <inline-formula> <tex-math notation="LaTeX">f </tex-math></inline-formula> is the value <inline-formula> <tex-math notation="LaTeX">f(V)=\Sigma _{u\in V(G)}f(u) </tex-math></inline-formula>. The total double Roman dominating function (TDRDF) on a graph <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula> without isolated vertices is a DRDF <inline-formula> <tex-math notation="LaTeX">f </tex-math></inline-formula> on <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula> with the additional condition that the subgraph of <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula> induced by the set <inline-formula> <tex-math notation="LaTeX">\{v\in V:~f(v)\ge 1\} </tex-math></inline-formula> is isolated-free. The total double Roman domination number <inline-formula> <tex-math notation="LaTeX">\gamma _{tdR}(G) </tex-math></inline-formula> is the smallest weight among all TDRDFs on <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula>. In this paper, we first show that the decision problem for the total double Roman domination is NP-hard for chordal and bipartite graphs, and then we establish some sharp bounds on total double Roman domination number.
In this paper, we survey results on the Roman domatic number and its variants in both graphs and digraphs. This fifth survey completes our works on Roman domination and its variations published in ...two book chapters and two other surveys.
A Roman dominating function (RD-function) on a graph
G
= (
V
,
E
) is a function
f
:
V
→ {0, 1, 2} satisfying the condition that every vertex
u
for which
f
(
u
) = 0 is adjacent to at least one ...vertex
v
for which
f
(
v
) = 2. An Roman dominating function
f
in a graph
G
is perfect Roman dominating function (PRD-function) if every vertex
u
with
f
(
u
) = 0 is adjacent to exactly one vertex
v
for which
f
(
v
) = 2. The (perfect) Roman domination number
γ
R
(
G
) (
γ
p
R
(
G
)) is the minimum weight of an (perfect) Roman dominating function on
G
. We say that
γ
p
R
(
G
) strongly equals
γ
R
(
G
), denoted by
γ
p
R
(
G
) ≡
γR
(
G
), if every RD-function on
G
of minimum weight is a PRD-function. In this paper we show that for a given graph
G
, it is NP-hard to decide whether
γ
p
R
(
G
) =
γR
(
G
) and also we provide a constructive characterization of trees
T
with
γ
p
R
(
T
) ≡
γR
(
T
).
PDF
