Postman tours and cycle covers

✍ Scribed by André Raspaud

• Book ID: 103056943
• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 509 KB
• Volume: 111
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90182-s

✦ Synopsis

Raspaud, A., Postman tours and cycle covers, Discrete Mathematics 111 (1993) 447-454.

Let G be a bridgeless graph. We show that the length of a shortest postman tour is at most IF(G)1 + 1 k'(G)1 -3 and that, if G is a minimally 2-edge connected graph, then the length is at most 21 V(G)l-2.

We then deduce results concerning the length of a shortest cycle cover for graphs containing no subdivision of the Petersen graph.