The P₃and P₄Decomposition Of Graphs

Abstract:The simple graphs which this paper researches are all finite、undirect-ed, and they don’t have the circle and overlap edges. At present, the problem that graph is decomposed paths with given length is researched widely. The path decom-posed of a graph is that a set of paths which each edge exactly appears in one of the paths. The path decomposition is a very important tool to solve graph theory problem. We can use the decomposition of graph to make complex problem more simple, so studying path decomposition is extremely significant.G is said to have subgraphs H decomposed if the edge set of graph G can be de-composed into a number of subgraphs H which the edges disjoint, and G has {P3, P4}-decomposition when H is P3or P4.This paper mainly researches some corona graphs and edge corona graphs which exist the problem of {-P3, P4}-decomposition, and according to fan graphs、wheel graphs and star graphs have {P3, P4}-decomposition, we show that corona graph and edge corona graph between path and circle; corona graph and edge corona graph between fan graphs and path; corona graph and edge corona graph between wheel graphs and circle; corona graph and edge corona graph between fan graphs and fan graphs; corona graph and edge corona graph between wheel graphs and wheel graphs, have the {P3, P4}-decomposition.