Unstable graphs and packing into fifth power.

In a graph G : = (V (G) , E (G)) , a subset M of the vertex set V (G) is a module (or interval, clan) of G if every vertex outside M is adjacent to all or none of M. The empty set, the singleton sets, and the full set of vertices are trivial modules. The graph G is indecomposable (or prime) if all its modules are trivial. If G is indecomposable, we say that an edge e of G is a removable edge if G − e is indecomposable (here G − e : = (V (G) , E (G) − { e })). The graph G is said to be unstable if it has no removable edges. For a positive integer k , the k th power G k of a graph G is the graph obtained from G by adding an edge between all pairs of vertices of G with distance at most k. A graph G of order n (i.e., | V (G) | = n) is said to be p -placeable into G k , if G k contains p edge-disjoint copies of G. In this paper, we answer a question, suggested by Boudabbous in a personal communication, concerning unstable graphs and packing into their fifth power as follows: First, we give a characterization of the unstable graphs which is deduced from the results given by Ehrenfeucht, Harju and Rozenberg (the theory of 2 -structures: a framework for decomposition and transformation of graphs). Second, we prove that every unstable graph G is 2 -placeable into G 5 . [ABSTRACT FROM AUTHOR]