Global defensive sets in graphs

详细信息    查看全文

• 作者：Robert Lewońup>aup>up> ; up>up>lewon.robert@gmail.com" class="auth_mail" title="E-mail the corresponding authorup> ; Anna Małafiejskaup>bup>up> ; up>up>anna@animima.org" class="auth_mail" title="E-mail the corresponding authorup> ; Michał Małafiejskiup>aup>up> ; up>up>michal@animima.org" class="auth_mail" title="E-mail the corresponding authorup>
• 关键词：Defensive set ; Alliance ; Domination ; NPNP-completeness
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 July 2016
• 年：2016
• 卷：339
• 期：7
• 页码：1861-1870
• 全文大小：483 K

文摘

In the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si33.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=a4fc3eafbcaec05161d6c23187493274" title="Click to view the MathML source">G$G$ and a subset ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si34.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=f547989a2e43ef83e4775584145d6679" title="Click to view the MathML source">S$S$ of a vertex set of ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si33.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=a4fc3eafbcaec05161d6c23187493274" title="Click to view the MathML source">G$G$, we define for every subset ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si36.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=3310ce01baade57c9d0cdd02513fa676" title="Click to view the MathML source">X$X$ of ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si34.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=f547989a2e43ef83e4775584145d6679" title="Click to view the MathML source">S$S$ the predicate ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si38.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=90255db745c4437647f53141bab46fe3" title="Click to view the MathML source">SEC(X)=true$SEC\left(X\right)=tr\mathrm{<font\; color="red">u</font>}e$ if and only if ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si39.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=706fbf1a85db97e3ca773bc87b1a44f6" title="Click to view the MathML source">|N[X]∩S|≥|N[X]∖S|$|N\left[X\right]\cap S|\ge |N\left[X\right]\setminus S|$ holds, where ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si40.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=19208de4994b3bd0ba1d2b0fa364ff54" title="Click to view the MathML source">N[X]$N\left[X\right]$ is a closed neighbourhood of ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si36.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=3310ce01baade57c9d0cdd02513fa676" title="Click to view the MathML source">X$X$ in graph ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si33.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=a4fc3eafbcaec05161d6c23187493274" title="Click to view the MathML source">G$G$. A set ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si34.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=f547989a2e43ef83e4775584145d6679" title="Click to view the MathML source">S$S$ is a defensive alliance   if and only if for each vertex ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si44.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=28c53d5415d49605784b259401635eb6" title="Click to view the MathML source">v∈S$v\in S$ we have ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si45.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=8f69efb274a71c7fb6a02d1acd6dd965" title="Click to view the MathML source">SEC({v})=true$SEC\left(\left\{v\right\}\right)=tr\mathrm{<font\; color="red">u</font>}e$. If ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si34.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=f547989a2e43ef83e4775584145d6679" title="Click to view the MathML source">S$S$ is also a dominating set of ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si33.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=a4fc3eafbcaec05161d6c23187493274" title="Click to view the MathML source">G$G$ (i.e., ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si48.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=c38f680aeba1d600c7e7729c538dff3d" title="Click to view the MathML source">N[S]=V(G)$N\left[S\right]=V\left(G\right)$), we say that ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si34.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=f547989a2e43ef83e4775584145d6679" title="Click to view the MathML source">S$S$ is a global defensive alliance.

We introduce the concept of defensive sets in graph ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si33.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=a4fc3eafbcaec05161d6c23187493274" title="Click to view the MathML source">G$G$ as follows: set ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si34.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=f547989a2e43ef83e4775584145d6679" title="Click to view the MathML source">S$S$ is a defensive set   in ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si33.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=a4fc3eafbcaec05161d6c23187493274" title="Click to view the MathML source">G$G$ if and only if for each vertex ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si44.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=28c53d5415d49605784b259401635eb6" title="Click to view the MathML source">v∈S$v\in S$ we have ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si45.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=8f69efb274a71c7fb6a02d1acd6dd965" title="Click to view the MathML source">SEC({v})=true$SEC\left(\left\{v\right\}\right)=tr\mathrm{<font\; color="red">u</font>}e$ or there exists a neighbour ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si55.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=b362f32a92fe95d6ba9817f8c248b5c8" title="Click to view the MathML source">u$\mathrm{<font\; color="red">u</font>}$ of ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si19.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=08863abf0970c5f21223a4395be3c2f8" title="Click to view the MathML source">v$v$ such that ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si57.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=ecf8ff85a65b1dbe9151ef72eaa39864" title="Click to view the MathML source">u∈S$\mathrm{<font\; color="red">u</font>}\in S$ and ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si58.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=53fab49bc41c6c34fed1c11c8f1312dc" title="Click to view the MathML source">SEC({v,u})=true$SEC\left(\{v,\mathrm{<font\; color="red">u</font>}\}\right)=tr\mathrm{<font\; color="red">u</font>}e$. Similarly, if ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si34.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=f547989a2e43ef83e4775584145d6679" title="Click to view the MathML source">S$S$ is also a dominating set of ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si33.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=a4fc3eafbcaec05161d6c23187493274" title="Click to view the MathML source">G$G$, we say that ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si34.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=f547989a2e43ef83e4775584145d6679" title="Click to view the MathML source">S$S$ is a global defensive set. We also study the problems of total dominating alliances (total alliances) and total dominating defensive sets (total defensive sets  ), i.e., ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si34.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=f547989a2e43ef83e4775584145d6679" title="Click to view the MathML source">S$S$ is a dominating set and the induced graph ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si63.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=c9063114f6c1d94841af742ea389273d" title="Click to view the MathML source">G[S]$G\left[S\right]$ has no isolated vertices.

In the paper we proved the ulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16300036&_mathId=si64.gif&_user=111111111&_pii=S0012365X16300036&_rdoc=1&_issn=0012365X&md5=3a38b3fd0ae8d77dacd49f4898031e0a" title="Click to view the MathML source">NP$\mathcal{NP}$-completeness for planar bipartite subcubic graphs of the decision versions of the following minimalization problems: a global and total alliance, a global and total defensive set. We proposed polynomial time algorithms solving in trees the problem of finding the minimum total and global defensive set and the total alliance. We obtained the lower bound on the minimum size of a global defensive set in arbitrary graphs and trees.