Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs

Hao Chen, Zihan Lei, Tian Liu (), Ziyang Tang, Chaoyi Wang and Ke Xu ()
Additional contact information
Hao Chen: Peking University
Zihan Lei: Peking University
Tian Liu: Peking University
Ziyang Tang: Peking University
Chaoyi Wang: Peking University
Ke Xu: Beihang University

Journal of Combinatorial Optimization, 2016, vol. 32, issue 1, No 7, 95-110

Abstract: Abstract Tree convex bipartite graphs generalize convex bipartite graphs by associating a tree, instead of a path, with one set of the vertices, such that for every vertex in another set, the neighborhood of this vertex induces a subtree. There are seven graph problems, grouped into three classes of domination, Hamiltonicity and treewidth, which are known to be $$\mathcal {NP}$$ NP -complete for bipartite graphs, but tractable for convex bipartite graphs. We show $$\mathcal {NP}$$ NP -completeness of these problems for tree convex bipartite graphs, even when the associated trees are stars or combs respectively.

Keywords: $$\mathcal {NP}$$ NP -completeness; Domination; Hamiltonianicity; Treewidth; Tree convex bipartite graphs (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9917-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:1:d:10.1007_s10878-015-9917-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9917-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().