Browsing by Subject "bipartite graphs"

Now showing 1 - 3 of 3

Access status: Open Access ,
A note on bipartite graphs whose [1,k]-domination number equal to their number of vertices
(Wydawnictwa AGH, 2020) Ghareghani, Narges; Peterin, Iztok; Sharifani, Pouyeh
A subset $D$ of the vertex set $V$ of a graph $G$ is called an $[1,k]$-dominating set if every vertex from $V-D$ is adjacent to at least one vertex and at most $k$ vertices of $D$. A $[1,k]$-dominating set with the minimum number of vertices is called a $\gamma_{[1,k]}$-set and the number of its vertices is the $[1,k]$-domination number $\gamma_{[1,k]}(G)$ of $G$. In this short note we show that the decision problem whether $\gamma_{[1,k]}(G)=n$ is an $NP$-hard problem, even for bipartite graphs. Also, a simple construction of a bipartite graph $G$ of order $n$ satisfying $\gamma_{[1,k]}(G)=n$ is given for every integer $n \geq (k+1)(2k+3)$.
Access status: Open Access ,
Cyclability in bipartite graphs
(2009) Amar, Denise; Flandrin, Evelyne; Gancarzewicz, Grzegorz
Let $G = (X,Y,E)$ be a balanced $2$-connected bipartite graph and $S \subset V(G)$. We will say that $S$ is cyclable in $G$ if all vertices of $S$ belong to a common cycle in $G$. We give sufficient degree conditions in a balanced bipartite graph $G$ and a subset $S \subset V(G)$ for the cyclability of the set $S$.
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.