On defensive alliances and line graphs

Simple item page
dc.creatorSigarreta, J. M.
dc.creatorRodriguez, J. A.
dc.date2006-02-20
dc.date.accessioned2026-07-07T07:03:36Z
dc.date.available2026-07-07T07:03:36Z
dc.descriptionLet $Γ$ be a simple graph of size $m$ and degree sequence $δ_1\ge δ_2\ge ... \ge δ_n$. Let ${\cal L}(Γ)$ denotes the line graph of $Γ$. The aim of this paper is to study mathematical properties of the alliance number, ${a}({\cal L}(Γ)$, and the global alliance number, $γ_{a}({\cal L}(Γ))$, of the line graph of a simple graph. We show that $\lceil\frac{δ_{n}+δ_{n-1}-1}{2}\rceil \le {a}({\cal L}(Γ))\le δ_1.$ In particular, if $Γ$ is a $δ$-regular graph ($δ>0$), then $a({\cal L}(Γ))=δ$, and if $Γ$ is a $(δ_1,δ_2)$-semiregular bipartite graph, then $a({\cal L}(Γ))=\lceil \frac{δ_1+δ_2-1}{2} \rceil$. As a consequence of the study we compare $a({\cal L}(Γ))$ and ${a}(Γ)$, and we characterize the graphs having $a({\cal L}(Γ))<4$. Moreover, we show that the global-connected alliance number of ${\cal L}(Γ)$ is bounded by $γ_{ca}({\cal L}(Γ)) \ge \lceil\sqrt{D(Γ)+m-1}-1\rceil,$ where $D(Γ)$ denotes the diameter of $Γ$, and we show that the global alliance number of ${\cal L}(Γ)$ is bounded by $γ_{a}({\cal L}(Γ))\geq \lceil\frac{2m}{δ_{1}+δ_{2}+1}\rceil$. The case of strong alliances is studied by analogy.
dc.identifierhttps://arxiv.org/abs/math/0602434
dc.identifierhttp://arxiv.org/abs/math/0602434
dc.identifierApplied Mathematics Letters 19 (12) (2006) 1345-1350
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/109037
dc.subjectCombinatorics
dc.subject05C69; 15C05
dc.titleOn defensive alliances and line graphs
dc.typetext

Files

Collections

arXiv