Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap

✍ Scribed by Noga Alon; Yair Caro; Raphael Yuster

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 360 KB
• Volume: 71
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1997.1768

✦ Synopsis

Let H=(V H , E H ) be a graph, and let k be a positive integer. A graph G=(V G , E G ) is H-coverable with overlap k if there is a covering of the edges of G by copies of H such that no edge of G is covered more than k times. Denote by overlap(H, G) the minimum k for which G is H-coverable with overlap k. The redundancy of a covering that uses t copies of H is (t|E

Our main result is the following: If H is a tree on h vertices and G is a graph with minimum degree $(G) (2h) 10 +C, where C is an absolute constant, then overlap(H, G) 2. Furthermore, one can find such a covering with overlap 2 and redundancy at most 1.5Â$(G) 0.1 . This result is tight in the sense that for every tree H on h 4 vertices and for every function f, the problem of deciding if a graph with $(G ) f (h) has overlap(H, G )=1 is NP-complete.

1997 Academic Press

1. Introduction

All graphs considered here are finite, undirected, and simple, unless otherwise noted. For the standard graph-theoretic notations the reader is referred to [2]. Let H be a graph, and let k be a positive integer. A graph

to H and every edge e # E appears in at least one member of L but in no more than k members of L. Denote by overlap(H, G) the minimum k for which G is H-coverable with overlap k. Clearly, overlap(H, G )=1 if and only if there is a decomposition of G into H. Also, if there is an edge of G which appears in no subgraph of G which is isomorphic to H, we put overlap(H, G )= . Clearly, if article no. TB971768 144 0095-8956Â97 25.00