On the Complexity of the P₃-Hull Number of the Cartesian Product of Graphs

详细信息    查看全文

• 作者：Julliano R. Nascimento^a ; ^{jullianorosanascimento@inf.ufg.br" class="auth_mail" title="E-mail the corresponding author} ; Erika M.M. Coelho^a ; ^{erikamorais@inf.ufg.br" class="auth_mail" title="E-mail the corresponding author} ; Hebert Coelho^a ; ^{hebert@inf.ufg.br" class="auth_mail" title="E-mail the corresponding author} ; Jayme L. Szwarcfiter^b ; ^c ; ^{jayme@nce.ufrj.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：P3P3-convexity ; P3P3-hull number ; Cartesian product
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：55
• 期：Complete
• 页码：169-172
• 全文大小：220 K

文摘

Let G be a finite, simple, and undirected graph and let S be a set of vertices of G. If no vertex of G that does not belong to S has two neighbors in S, then S   is class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301986&_mathId=si1.gif&_user=111111111&_pii=S1571065316301986&_rdoc=1&_issn=15710653&md5=96ff73e5ebf9901b87e8c36fdd1b0606" title="Click to view the MathML source">P₃class="mathContainer hidden">class="mathCode">$P_3$-convex. The class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301986&_mathId=si1.gif&_user=111111111&_pii=S1571065316301986&_rdoc=1&_issn=15710653&md5=96ff73e5ebf9901b87e8c36fdd1b0606" title="Click to view the MathML source">P₃class="mathContainer hidden">class="mathCode">$P_3$-convex hull class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301986&_mathId=si2.gif&_user=111111111&_pii=S1571065316301986&_rdoc=1&_issn=15710653&md5=0626efe9e513daebf4ae76cd593959de" title="Click to view the MathML source">H(S)class="mathContainer hidden">class="mathCode">$H(S)$ of S   is the smallest class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301986&_mathId=si1.gif&_user=111111111&_pii=S1571065316301986&_rdoc=1&_issn=15710653&md5=96ff73e5ebf9901b87e8c36fdd1b0606" title="Click to view the MathML source">P₃class="mathContainer hidden">class="mathCode">$P_3$-convex set containing S  . If class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301986&_mathId=si3.gif&_user=111111111&_pii=S1571065316301986&_rdoc=1&_issn=15710653&md5=c1caba0167de713dc9cf3b4fcd9ec028" title="Click to view the MathML source">H(S)=V(G)class="mathContainer hidden">class="mathCode">$H(S)=V(G)$ we say that S   is a class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301986&_mathId=si1.gif&_user=111111111&_pii=S1571065316301986&_rdoc=1&_issn=15710653&md5=96ff73e5ebf9901b87e8c36fdd1b0606" title="Click to view the MathML source">P₃class="mathContainer hidden">class="mathCode">$P_3$-hull set of G  . The cardinality class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301986&_mathId=si4.gif&_user=111111111&_pii=S1571065316301986&_rdoc=1&_issn=15710653&md5=b1d9495b31aaf036533c41fdb3c4bcf1" title="Click to view the MathML source">h(G)class="mathContainer hidden">class="mathCode">$h(G)$ of a minimum class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301986&_mathId=si1.gif&_user=111111111&_pii=S1571065316301986&_rdoc=1&_issn=15710653&md5=96ff73e5ebf9901b87e8c36fdd1b0606" title="Click to view the MathML source">P₃class="mathContainer hidden">class="mathCode">$P_3$-hull set in G   is called the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301986&_mathId=si1.gif&_user=111111111&_pii=S1571065316301986&_rdoc=1&_issn=15710653&md5=96ff73e5ebf9901b87e8c36fdd1b0606" title="Click to view the MathML source">P₃class="mathContainer hidden">class="mathCode">$P_3$-hull number of G. In this paper w extend the result of Centeno et al. [Theoretical Computer Science 412 (2011), 3693–3700] showing that, given a graph G and an integer k  , deciding whether class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301986&_mathId=si5.gif&_user=111111111&_pii=S1571065316301986&_rdoc=1&_issn=15710653&md5=078ef96d68cee8b57a3902d9ac9c0179" title="Click to view the MathML source">h(G)≤kclass="mathContainer hidden">class="mathCode">$h(G)\le k$ remains NP-complete for the Cartesian product of graphs.