Complexity aspects of the triangle path convexity

详细信息    查看全文

• 作者：Mitre C. Dourado^a ; ^{mitre@nce.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; Rudini M. Sampaio^b ; ^{rudini@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Convexity number ; Graph convexity ; Hull number ; Triangle path convexity
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：19 June 2016
• 年：2016
• 卷：206
• 期：Complete
• 页码：39-47
• 全文大小：402 K

文摘

In a triangle path  class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si28.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=dc4373f527f72eed0401fa55c5847957" title="Click to view the MathML source">v₁,…,v_tclass="mathContainer hidden">class="mathCode">$v_1,\dots ,v_t$ of a graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si29.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=1cfaf13561f55df2759dc5239faf0f46" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ no edges exist joining vertices class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si30.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=ac327e9415f68e610e8554fa080af6c6" title="Click to view the MathML source">v_iclass="mathContainer hidden">class="mathCode">$v_i$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si31.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=97ee13eabc7eb5ec18b4101694199e39" title="Click to view the MathML source">v_jclass="mathContainer hidden">class="mathCode">$v_j$ such that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si32.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=7bafab307651de0da49070ec850de639" title="Click to view the MathML source">|j−i|>2class="mathContainer hidden">class="mathCode">$|j-i|>2$. A set class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si33.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=5f03b66691516d203b697acb69f58cfa" title="Click to view the MathML source">S⊆V(G)class="mathContainer hidden">class="mathCode">$S\subseteq V\left(G\right)$ is convex in the triangle path convexity of   class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si29.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=1cfaf13561f55df2759dc5239faf0f46" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$, or class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si35.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=722ae2d6e8da6fce108b3f1c787f3a5a" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$-convex  , if the vertices of every triangle path joining two vertices of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si36.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=7e04c549a0ca1bc69456bda19b776f41" title="Click to view the MathML source">Sclass="mathContainer hidden">class="mathCode">$S$ are in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si36.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=7e04c549a0ca1bc69456bda19b776f41" title="Click to view the MathML source">Sclass="mathContainer hidden">class="mathCode">$S$. The cardinality of a maximum proper class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si35.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=722ae2d6e8da6fce108b3f1c787f3a5a" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$-convex subset of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si39.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=b19da54e0a6a5b5c1157776faf43f704" title="Click to view the MathML source">V(G)class="mathContainer hidden">class="mathCode">$V\left(G\right)$ is the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si35.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=722ae2d6e8da6fce108b3f1c787f3a5a" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$-convexity number of   class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si29.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=1cfaf13561f55df2759dc5239faf0f46" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ and the cardinality of a minimum set of vertices whose class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si35.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=722ae2d6e8da6fce108b3f1c787f3a5a" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$-convex hull is class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si39.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=b19da54e0a6a5b5c1157776faf43f704" title="Click to view the MathML source">V(G)class="mathContainer hidden">class="mathCode">$V\left(G\right)$ is the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si35.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=722ae2d6e8da6fce108b3f1c787f3a5a" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$-hull number of   class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si29.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=1cfaf13561f55df2759dc5239faf0f46" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$. We solve the fundamental complexity problems on the triangle path convexity. Among them, we present polynomial-time algorithms for determining the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si35.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=722ae2d6e8da6fce108b3f1c787f3a5a" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$-convexity number and the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300026&_mathId=si35.gif&_user=111111111&_pii=S0166218X16300026&_rdoc=1&_issn=0166218X&md5=722ae2d6e8da6fce108b3f1c787f3a5a" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$-hull number of a general graph.