P-3-equicoverable graphs - Research on H-equicoverable graphs

摘要

Let H be a fixed graph. An H-covering of G is a set L = {H-1, H-2,..., H-k} of subgraphs of G, where each subgraph H-i is isomorphic to H and every edge of G appears in at least one member of L. If there exists an H-covering of G, G is called H-coverable. An H-covering of G with k copies H-1, H-2,..., H-k of H is called ndninial if, for any H-j, boolean OR(k)(i=1) H-i - H-j is not an H-covering of G. An H-covering of G with k copies H-1, H-2,..., H-k of H is called minimum if there exists no H-covering with less than k copies of H. A graph G is called H-equicoverable if every minimal H-covering in G is also a minimum H-covering in G. In this paper, we investigate the characterization of P-3-equicoverable graphs. (c) 2007 Elsevier B.V. All rights reserved.