Partitions of a graph into paths with prescribed endvertices and lengths

✍ Scribed by Hikoe Enomoto; Katsuhiro Ota

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 95 KB
• Volume: 34
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/1097-0118(200006)34:2<163::aid-jgt5>3.0.co;2-k

✦ Synopsis

For a graph G, let ' 2 (G ) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| n i 1 k a i and ' 2 (G ) ! n k À 1, then for any k vertices v 1 , v 2 , F F F , v k in G, there exist vertex-disjoint paths P 1 , P 2 , F F F , P k such that |V (P i )| a i and v i is an endvertex of P i for 1 i k. In this paper, we verify the conjecture for the cases where almost all a i 5, and the cases where k 3.