Browsing by Author "Chellali, Mustapha"

Now showing 1 - 9 of 9

Access status: Open Access ,
A note on a relation between the weak and strong domination numbers of a graph
(2012) Boutrig, Razika; Chellali, Mustapha
In a graph $G=(V,E)$ a vertex is said to dominate itself and all its neighbors. A set $D \subset V$ is a weak (strong, respectively) dominating set of $G$ if every vertex $v \in V-S$ is adjacent to a vertex $u \in D$ such that $d_G(v) \geq d_G(u)$ $d_G(v) \leq d_G(u)$, respectively). The weak (strong, respectively) domination number of $G$, denoted by $\gamma_w(G)$ $(\gamma_s(G)$, respectively), is the minimum cardinality of a weak (strong, respectively) dominating set of $G$. In this note we show that if $G$ is a connected graph of order $n \geq 3$, then $\gamma_w(G) + t\gamma_s(G) \leq n$, where $t=3/(\Delta+1)$ if $G$ is an arbitrary graph, $t=3/5$ if $G$ is a block graph, and $t=2/3$ if $G$ is a claw free graph.
Access status: Open Access ,
A note on global alliances in trees
(2011) Bouzefrane, Mohamed; Chellali, Mustapha
For a graph $G=(V,E)$, a set $S\subseteq V$ is a dominating set if every vertex in $V - S$ has at least a neighbor in $S$. A dominating set $S$ is a global offensive (respectively, defensive) alliance if for each vertex in $V - S$ (respectively, in $S$) at least half the vertices from the closed neighborhood of $v$ are in $S$. The domination number $\gamma(G)$ is the minimum cardinality of a dominating set of $G$, and the global offensive alliance number $\gamma_{o}(G)$ (respectively, global defensive alliance number $\gamma_{a}(G)$) is the minimum cardinality of a global offensive alliance (respectively, global deffensive alliance) of $G$. We show that if $T$ is a tree of order $n$, then $\gamma_{o}(T)\leq 2\gamma(T)-1$ and if $n\geq 3$, then $\gamma_{o}(T)\leq \frac{3}{2}\gamma_{a}(T)-1$. Moreover, all extremal trees attaining the first bound are characterized.
Access status: Open Access ,
A note on k-Roman graphs
(2013) Bouchou, Ahmed; Blidia, Mostafa; Chellali, Mustapha
Let $G=(V,E)$ be a graph and let $k$ be a positive integer. A subset $D$ of $V(G)$ is a $k$-dominating set of $G$ if every vertex in $V\left( G\right) \backslash D$ has at least $k$ neighbours in $D$. The $k$-domination number $\gamma_{k}(G)$ is the minimum cardinality of a $k$-dominating set of $G$. A Roman $k$-dominating function on $G$ is a function $f\colon V(G)\longrightarrow\{0,1,2\}$ such that every vertex u for which $f(u)=0$ is adjacent to at least $k$ vertices $v_{1},v_{2},\ldots ,v_{k}$ with $f(v_{i})=2$ for $i=1,2,\ldots ,k.$ The weight of a Roman $k$-dominating function is the value $f(V(G))=\sum_{u\in V(G)}f(u)$ and the minimum weight of a Roman $k$-dominating function on $G$ is called the Roman $k$-domination number $\gamma_{kR}\left( G\right)$ of $G$. A graph $G$ is said to be a $k$-Roman graph if $\gamma_{kR}(G)=2\gamma_{k}(G).$ In this note we study $k$-Roman graphs.
Access status: Open Access ,
A note on the independent Roman domination in unicyclic graphs
(2012) Chellali, Mustapha; Rad, Nader Jafari
A Roman dominating function (RDF) on a graph $G=(V;E)$ is a function $f : V \to \{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$. The weight of an RDF is the value $f(V(G)) = \sum _{u \in V (G)} f(u)$. An RDF $f$ in a graph $G$ is independent if no two vertices assigned positive values are adjacent. The Roman domination number $\gamma _R (G)$ (respectively, the independent Roman domination number $i_{R}(G)$) is the minimum weight of an RDF (respectively, independent RDF) on $G$. We say that $\gamma _R (G)$ strongly equals $i_{R}(G)$), denoted by $\gamma _R (G) \equiv i_R (G)$, if every RDF on $G$ of minimum weight is independent. In this note we characterize all unicyclic graphs $G$ with $\gamma _R (G) \equiv i_R (G).$
Access status: Open Access ,
A note on Vizing's generalized conjecture
(2007) Blidia, Mostafa; Chellali, Mustapha
In this note we give a generalized version of Vizing's conjecture concerning the distance domination number for the cartesian product of two graphs.
Access status: Open Access ,
Bounds on the 2-domination number in cactus graphs
(2006) Chellali, Mustapha
A $2$-dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex not in $S$ is dominated at least twice. The minimum cardinality of a $2$-dominating set of $G$ is the $2$-domination number $\gamma_{2}(G)$. We show that if $G$ is a nontrivial connected cactus graph with $k(G)$ even cycles ($k(G)\geq 0$), then $\gamma_{2}(G)\geq\gamma_{t}(G)-k(G)$, and if $G$ is a graph of order n with at most one cycle, then $\gamma_{2}(G)\geqslant(n+\ell-s)/2$ improving Fink and Jacobson's lower bound for trees with $\ell>s$, where $\gamma_{t}(G)$, $\ell$ and $s$ are the total domination number, the number of leaves and support vertices of $G$, respectively. We also show that if $T$ is a tree of order $n\geqslant 3$, then $\gamma_{2}(T)\leqslant\beta(T)+s-1$, where $\beta(T)$ is the independence number of $T$.
Access status: Open Access ,
Global offensive k-alliance in bipartite graphs
(2012) Chellali, Mustapha; Volkmann, Lutz
Let $k \geq 0$ be an integer. A set $S$ of vertices of a graph $G=(V(G),E(G))$ is called a global offensive $k$-alliance if $|N(v) \cap S| \geq |N(v) \cap S|+k$ for every $v \in V(G)-S$, where $0 \leq k \leq \Delta$ and $\Delta$ is the maximum degree of $G$. The global offensive $k$-alliance number $\gamma^{k}_{o}(G)$ is the minimum cardinality of a global offensive $k$-alliance in $G$. We show that for every bipartite graph $G$ and every integer $k \geq 2$, $\gamma^k_o(G) \leq \frac{n(G)+|L_k(G)|}{2}$, where $L_{k}(G)$ is the set of vertices of degree at most $k - 1$. Moreover, extremal trees attaining this upper bound are characterized.
Access status: Open Access ,
On the global offensive alliance number of a tree
(2009) Bouzefrane, Mohamed; Chellali, Mustapha
For a graph $G=(V,E)$, a set $S \subseteq V$ is a dominating set if every vertex in $V - S$ has at least a neighbor in $S$. A dominating set $S$ is a global offensive alliance if for every vertex $v$ in $V - S$, at least half of the vertices in its closed neighborhood are in $S$. The domination number $\gamma(G)$ is the minimum cardinality of a dominating set of $G$ and the global offensive alliance number $\gamma_o(G)$ is the minimum cardinality of a global offensive alliance of $G$. We first show that every tree of order at least three with $l$ leaves and $s$ support vertices satisfies $\gamma_o(T) \geq (n-l+s+1)/3$ and we characterize extremal trees attaining this lower bound. Then we give a constructive characterization of trees with equal domination and global offensive alliance numbers.
Access status: Open Access ,
Trees with equal global offensive k-alliance and k-domination numbers
(2010) Chellali, Mustapha
Let $k \geq 1$ be an integer. A set $S$ of vertices of a graph $G=(V(G),E(G))$ is called a global offensive $k$-alliance if $|N(v) \cap S| \geq |N(v) - S| + k$ for every $v \in V(G)- S$, where $N(v)$ is the neighborhood of $v$. The subset $S$ is a $k$-dominating set of $G$ if every vertex in $V(G) - S$ has at least $k$ neighbors in $S$. The global offensive $k$-alliance number $\gamma_0^k (G)$ is the minimum cardinality of a global offensive $k$-alliance in $G$ and the $k$-domination number $\gamma _k (G)$ is the minimum cardinality of a $k$-dominating set of $G$. For every integer $k \geq 1$ every graph $G$ satisfies $\gamma_0^k (G) \geq \gamma_k (G)$. In this paper we provide for $k \geq 2$ a characterization of trees $T$ with equal $\gamma_0^k (T)$ and $\gamma_k (T)$.