首页 | 本学科首页   官方微博 | 高级检索  
     检索      

TREE DECOMPOSITIONS OF MULTIGRAPHS
作者姓名:SHI  Minyong
作者单位:Department of Computer Science and Technology,Beijing Broadcasting Institute,Beijing 100024,China
摘    要:1.IntroductionInthispaperweconsideronlyfiniteundirectedlooplessgraphs.ForasubgraphHofG,E(H)andP(H)denotethenumberofedgesandthenUmberofcyclesinHrespectively.GiventwodisjointsubsetsXandYofV(G),wewriteEG(X,Y)={acEE(G)IxEX,y6Y}.IfTisatreeinGande=acEG--E(T)with{u,v}CV(T),thenT econtainsauniquecycle.WedenotethiscyclebyC(T,e).Aforestiscalledak-tree-forestifitconsistsofexactlykpairwisedisjointtrees.ForagraphG,ifE(G)canbepartitionedilltoseveralpairwisedisjointsetsas{EI,EZ,...,EI}such…


TREE DECOMPOSITIONS OF MULTIGRAPHS
SHI Minyong.TREE DECOMPOSITIONS OF MULTIGRAPHS[J].Journal of Systems Science and Complexity,1999(3).
Authors:SHI Minyong
Abstract: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.
Keywords:Tree decomposition  (k  l) graphs  Pk-graph  maximal planar bipartitegraph  maximal planar graph
本文献已被 CNKI 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号