On defensive alliances and line graphs

Abstract

Let $\Gamma$ be a simple graph of size $m$ and degree sequence ${\delta }_1\ge {\delta }_2\ge ...\ge {\delta }_n$. Let $\mathcal{L}(\Gamma )$ denotes the line graph of $\Gamma$. The aim of this paper is to study mathematical properties of the alliance number, $a(\mathcal{L}(\Gamma )$, and the global alliance number, ${\gamma }_a(\mathcal{L}(\Gamma ))$, of the line graph of a simple graph. We show that $\lceil \frac{{\delta }_n+{\delta }_{n-1}-1}{2}\rceil \le a(\mathcal{L}(\Gamma ))\le {\delta }_1.$ In particular, if $\Gamma$ is a $\delta$-regular graph ($\delta >0$), then $a(\mathcal{L}(\Gamma ))=\delta$, and if $\Gamma$ is a $({\delta }_1,{\delta }_2)$-semiregular bipartite graph, then $a(\mathcal{L}(\Gamma ))=\lceil \frac{{\delta }_1+{\delta }_2-1}{2}\rceil$. As a consequence of the study we compare $a(\mathcal{L}(\Gamma ))$ and $a(\Gamma )$, and we characterize the graphs having $a(\mathcal{L}(\Gamma ))<4$. Moreover, we show that the global-connected alliance number of $\mathcal{L}(\Gamma )$ is bounded by ${\gamma }_{ca}(\mathcal{L}(\Gamma ))\ge \lceil \sqrt{D(\Gamma )+m-1}-1\rceil ,$ where $D(\Gamma )$ denotes the diameter of $\Gamma$, and we show that the global alliance number of $\mathcal{L}(\Gamma )$ is bounded by ${\gamma }_a(\mathcal{L}(\Gamma ))\ge \lceil \frac{2m}{{\delta }_1+{\delta }_2+1}\rceil$. The case of strong alliances is studied by analogy.