Browsing by Subject "trees"

Now showing 1 - 11 of 11

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 the p-domination number of trees
(2009) Lu, You; Hou, Xinmin; Xu, Jun-Ming
Let $p$ be a positive integer and $G=(V(G),E(G))$ a graph. A $p$-dominating set of $G$ is a subset $S$ of $V(G)$ such that every vertex not in $S$ is dominated by at least $p$ vertices in $S$. The $p$-domination number $\gamma_p(G)$ is the minimum cardinality among the p-dominating sets of $G$. Let $T$ be a tree with order $n \geq 2$ and $p \geq 2$ a positive integer. A vertex of $V(T)$ is a $p$-leaf if it has degree at most $p - 1$, while a $p$-support vertex is a vertex of degree at least $p$ adjacent to a $p$-leaf. In this note, we show that $\gamma_p(T) \geq (n + |L_p(T)|-|S_p(T)|)/2$, where $L_{p}(T)$ and $S_{p}(T)$ are the sets of $p$-leaves and $p$-support vertices of $T$, respectively. Moreover, we characterize all trees attaining this lower bound.
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 ,
Classical solutions of initial problems for quasilinear partial functional differential equations of the first order
(2006) Czernous, Wojciech
We consider the initial problem for a quasilinear partial functional differential equation of the first order $\partial_t z(t,x)+\sum_{i=1}^nf_i(t,x,z_{(t,x)})\partial_{x_i} z(t,x)=G(t,x,z_{(t,x)}),\\ z(t,x)=\varphi(t,x)\;\;((t,x)\in[-h_0,0]\times R^n)$ where $z_{(t,x)}\colon\,[-h_0,0]\times[-h,h]\to R$ is a function defined by $z_{(t,x)}(\tau,\xi)=z(t+\tau,x+\xi)$ for $(\tau,\xi)\in[-h_0,0]\times[-h,h]$. Using the method of bicharacteristics and the fixed-point theorem we prove, under suitable assumptions, a theorem on the local existence and uniqueness of classical solutions of the problem and its continuous dependence on the initial condition.
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 ,
Improving Traffic-noise-mitigation Strategies with LiDAR-based 3D Tree-canopy Analysis
(Wydawnictwa AGH, 2024) Wickramathilaka, Nevil; Ujang, Uznir; Azri, Suhaibah
The leaves on trees absorb road noise and serve as noise barriers. Tree structures such as tree belts and isolated trees have various methods for absorbing sounds. The depth, surface area, and noise-absorption coefficient of trees contribute to noise absorption. Therefore, this study aims to address this issue of traffic-noise pollution through the use of trees, in particular, by analyzing the noise-absorption coefficient of leaves, the surface area of the leaves, and the depths of the trees. However, the study stresses the need for 3D tree-canopy visualization to identify these factors. To achieve this, the study used LiDAR point clouds to provide accurate data for the convex hull visualizations of canopies. Additionally, a formulated equation for calculating traffic noise after absorption has been suggested by combining the traffic-noise absorption and Henk de Kluijver traffic-noise models. The study also compares the effectiveness of tree belts and isolated trees in reducing noise pollution, concluding that, below a canopy of trees, there is no noise reduction. Finally, the study has demonstrated that the number and sizes of leaves affect noise absorption, showing that noise pollution can be reduced by 1 to 3 dB(A) in the research area by using trees.
Access status: Restricted ,
Kształt drzew dowolnie podzielnych
(Data obrony: 2013-06-25) Fałda, Łukasz
Wydział Matematyki Stosowanej
Access status: Open Access ,
On domination multisubdivision number of unicyclic graphs
(Wydawnictwa AGH, 2018) Raczek, Joanna
The paper continues the interesting study of the domination subdivision number and the domination multisubdivision number. On the basis of the constructive characterization of the trees with the domination subdivision number equal to 3 given in [H. Aram, S.M. Sheikholeslami, O. Favaron, Domination subdivision number of trees, Discrete Math. 309 (2009), 622-628], we constructively characterize all connected unicyclic graphs with the domination multisubdivision number equal to 3. We end with further questions and open problems.
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 ,
Outer independent rainbow dominating functions in graphs
(Wydawnictwa AGH, 2020) Mansouri, Zhila; Mojdeh, Doost Ali
A 2-rainbow dominating function (2-rD function) of a graph $G=(V,E)$ is a function $f:V(G)\rightarrow\{\emptyset,\{1\},\{2\},\{1,2\}\}$ having the property that if $f(x)=\emptyset$, then $f(N(x))=\{1,2\}$. The 2-rainbow domination number $\gamma_{r2}(G)$ is the minimum weight of $\sum_{v\in V(G)}|f(v)|$ taken over all 2-rainbow dominating functions $f$. An outer-independent 2-rainbow dominating function (OI2-rD function) of a graph $G$ is a 2-rD function $f$ for which the set of all $v \in V(G)$ with $f(v)=\emptyset$ is independent. The outer independent 2-rainbow domination number $\gamma_{oir2}(G)$ is the minimum weight of an OI2-rD function of $G$. In this paper, we study the OI2-rD number of graphs. We give the complexity of the problem OI2-rD of graphs and present lower and upper bounds on $\gamma_{oir2}(G)$. Moreover, we characterize graphs with some small or large OI2-rD numbers and we also bound this parameter from above for trees in terms of the order, leaves and the number of support vertices and characterize all trees attaining the bound. Finally, we show that any ordered pair $(a,b)$ is realizable as the vertex cover number and OI2-rD numbers of some non-trivial tree if and only if $a+1\leq b\leq 2a$.
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)$.