Source author record

Sergio Bermudo

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2011arXiv

Alliance free sets in Cartesian product graphs

Let $G=(V,E)$ be a graph. For a non-empty subset of vertices $S\subseteq V$ , and vertex $v\in V$ , let $δ_S(v)=|\{u\in S:uv\in E\}|$ denote the cardinality of the set of neighbors of $v$ in $S$ , and let $\bar{S}=V-S$ . Consider the following condition: {equation}\label{alliancecondition} δ_S(v)\ge δ_{\bar{S}}(v)+k, \{equation} which states that a vertex $v$ has at least $k$ more neighbors in $S$ than it has in $\bar{S}$ . A set $S\subseteq V$ that satisfies Condition (\ref{alliancecondition}) for every vertex $v \in S$ is called a \emph{defensive} $k$ -\emph{alliance}; for every vertex $v$ in the neighborhood of $S$ is called an \emph{offensive} $k$ -\emph{alliance}. A subset of vertices $S\subseteq V$ , is a \emph{powerful} $k$ -\emph{alliance} if it is both a defensive $k$ -alliance and an offensive $(k +2)$ -alliance. Moreover, a subset $X\subset V$ is a defensive (an offensive or a powerful) $k$ -alliance free set if $X$ does not contain any defensive (offensive or powerful, respectively) $k$ -alliance. In this article we study the relationships between defensive (offensive, powerful) $k$ -alliance free sets in Cartesian product graphs and defensive (offensive, powerful) $k$ -alliance free sets in the factor graphs.

preprint2010arXiv

Partitioning a graph into defensive k-alliances

A defensive $k$ -alliance in a graph is a set $S$ of vertices with the property that every vertex in $S$ has at least $k$ more neighbors in $S$ than it has outside of $S$ . A defensive $k$ -alliance $S$ is called global if it forms a dominating set. In this paper we study the problem of partitioning the vertex set of a graph into (global) defensive $k$ -alliances. The (global) defensive $k$ -alliance partition number of a graph $Γ=(V,E)$ , ( $ψ_{k}^{gd}(Γ)$ ) $ψ_k^{d}(Γ)$ , is defined to be the maximum number of sets in a partition of $V$ such that each set is a (global) defensive $k$ -alliance. We obtain tight bounds on $ψ_k^{d}(Γ)$ and $ψ_{k}^{gd}(Γ)$ in terms of several parameters of the graph including the order, size, maximum and minimum degree, the algebraic connectivity and the isoperimetric number. Moreover, we study the close relationships that exist among partitions of $Γ_1\times Γ_2$ into (global) defensive $(k_1+k_2)$ -alliances and partitions of $Γ_i$ into (global) defensive $k_i$ -alliances, $i\in \{1,2\}$ .

preprint2009arXiv

On global offensive k-alliances in graphs

We investigate the relationship between global offensive $k$ -alliances and some characteristic sets of a graph including $r$ -dependent sets and $τ$ -dominating sets. As a consequence of the study, we obtain bounds on the global offensive $k$ -alliance number in terms of several parameters of the graph.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.