General-demand disjoint path covers in a graph with faulty elements

Abstract

A k-disjoint path cover of a graph is a set of k internally vertex-disjoint paths which cover the vertex set with k paths and each of which runs between a source and a sink. Given that each source and sink v is associated with an integer-valued demand d(v)≥1, we are concerned with general-demand k-disjoint path cover in which every source and sink v is contained in the d(v) paths. In this paper, we present a reduction of a general-demand disjoint path cover problem to an unpaired many-to-many disjoint path cover problem, and obtain some results on disjoint path covers of restricted HL-graphs and proper interval graphs with faulty vertices and/or edges.

Keywords:

• disjoint paths
• Menger's theorem
• Fan lemma
• hypercube-like graphs
• proper interval graphs

2010 AMS Subject Classifications :

• 05C38
• 05C40
• 05C45
• 68R10
• 90B18

Acknowledgements

We are grateful to the anonymous reviewers for their comments and suggestions. This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) (KRF-2008-521-D00363).