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 P₉$P_9$-free graph is NP-hard. Similarly, we show that computing the geodetic interval number of a given P₅$P_5$-free graph is NP-hard. Furthermore, we show that the geodetic hull number can be computed in polynomial time for {paw,P₅}$\{\mathrm{paw},P_5\}$-free graphs, triangle-free graphs in which every six vertices induce at most one P₅$P_5$, and {C₃,…,C_k−2,P_k}$\{C_3,\dots ,C_{k-2},P_k\}$-free graphs for every integer k.