TREE DECOMPOSITIONS OF MULTIGRAPHS  

作　　者：SHI Minyong(Department of Computer Science and Technology,Beijing Broadcasting Institute, Beijing 100024, China) 

出　　处：《Systems Science and Mathematical Sciences》1999年第3期231-237,共7页

摘　　要：For a graph G, if E(G) can be partitioned into several pairwise disjoint sets as{E1 , E2,...,El } such that the subgraph induced by Ei is a tree of order ki ) (i = 1, 2,... , l),then G is said to have a {k1, k2, ..., kl }-tree-decomposition, denoted by { k1, k2 ,..., Kl } G.For k 1 and l 0, a collection (k,l) is the set of multigraphs such that G e Q(k,l)if and only if e(G) = k(G - 1) - l and (H) max{(k - 1)(H - 1),k(H -1) -l}for any subgraph H of G. We Prove that (1) If k 2,0 l 3 and G Q(k,l) oforder + 1, then {n,n,...,n -- l} E G. (2) If 2 and G (k,2) of ordern 3, then {n,n, ...,n,n-- 2} E G and {n,n,.. -1,n - 1} G. (3) If 3 andG g(k,3) of order n 4, then {n, n,... n,n-- 3} G ) {n,n,.., n,n-- 1,n -- 2} Gand {n,n,... n,n -- 1,n -- 1,n -- 1} G.For a graph G, if E(G) can be partitioned into several pairwise disjoint sets as{E1 , E2,...,El } such that the subgraph induced by Ei is a tree of order ki ) (i = 1, 2,... , l),then G is said to have a {k1, k2, ..., kl }-tree-decomposition, denoted by { k1, k2 ,..., Kl } G.For k 1 and l 0, a collection (k,l) is the set of multigraphs such that G e Q(k,l)if and only if e(G) = k(G - 1) - l and (H) max{(k - 1)(H - 1),k(H -1) -l}for any subgraph H of G. We Prove that (1) If k 2,0 l 3 and G Q(k,l) oforder + 1, then {n,n,...,n -- l} E G. (2) If 2 and G (k,2) of ordern 3, then {n,n, ...,n,n-- 2} E G and {n,n,.. -1,n - 1} G. (3) If 3 andG g(k,3) of order n 4, then {n, n,... n,n-- 3} G ) {n,n,.., n,n-- 1,n -- 2} Gand {n,n,... n,n -- 1,n -- 1,n -- 1} G.

关 键 词：TREE decomposition (k l) GRAPHS Pk-graph MAXIMAL PLANAR bipartitegraph MAXIMAL PLANAR GRAPH 

分 类 号：O157[理学—数学]