On the geodetic hull number of P_k-free graphs

详细信息    查看全文

• 作者：Mitre C. Dourado^a ; ^{mitre@dcc.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; Lucia D. Penso^b ; ^{lucia.penso@uni-ulm.de" class="auth_mail" title="E-mail the corresponding author} ; Dieter Rautenbach^b ; ^{dieter.rautenbach@uni-ulm.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Geodetic convexity ; Hull number ; Geodetic number ; Interval number ; PkPk-free graphs
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：9 August 2016
• 年：2016
• 卷：640
• 期：Complete
• 页码：52-60
• 全文大小：362 K

文摘

Partially answering a question posed by Araujo, Morel, Sampaio, Soares, and Weber, we show that computing the geodetic hull number of a given class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516302341&_mathId=si1.gif&_user=111111111&_pii=S0304397516302341&_rdoc=1&_issn=03043975&md5=4765fb4a04a44b8d3aaf57123a21e3a1" title="Click to view the MathML source">P₉class="mathContainer hidden">class="mathCode">$P_9$-free graph is NP-hard. Similarly, we show that computing the geodetic interval number of a given class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516302341&_mathId=si132.gif&_user=111111111&_pii=S0304397516302341&_rdoc=1&_issn=03043975&md5=8c253ab9f5b7d5cf7230d080bbd10eea" title="Click to view the MathML source">P₅class="mathContainer hidden">class="mathCode">$P_5$-free graph is NP-hard. Furthermore, we show that the geodetic hull number can be computed in polynomial time for class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516302341&_mathId=si169.gif&_user=111111111&_pii=S0304397516302341&_rdoc=1&_issn=03043975&md5=bc926664f7eb60bac6977e4d69ce2819" title="Click to view the MathML source">{paw,P₅}class="mathContainer hidden">class="mathCode">$\{\mathrm{paw},P_5\}$-free graphs, triangle-free graphs in which every six vertices induce at most one class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516302341&_mathId=si132.gif&_user=111111111&_pii=S0304397516302341&_rdoc=1&_issn=03043975&md5=8c253ab9f5b7d5cf7230d080bbd10eea" title="Click to view the MathML source">P₅class="mathContainer hidden">class="mathCode">$P_5$, and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516302341&_mathId=si4.gif&_user=111111111&_pii=S0304397516302341&_rdoc=1&_issn=03043975&md5=8a8650a96608018768adab553eb12b90" title="Click to view the MathML source">{C₃,…,C_k−2,P_k}class="mathContainer hidden">class="mathCode">$\{C_3,\dots ,C_{k-2},P_k\}$-free graphs for every integer k.