（应用数学专业论文）关于非完全覆盖图的重构.pdf

摘要 令f = ( y ( r ) ，e ( r ) ) 表示一个以v ( r ) 为点集，e ( r ) 为边集的有限非空无 向图对于任意一个非负整数s 及v ( r ) 上的一个8 + 1 一序列0 f = ( o l o ，q 。) ， 0 f 称为f 上的一条s 一弧，如果 o l ，o q + i ) e ( r ) ，对于i = 0 ，1 ，8 1 ，并且 o l i l q 件1 ，对于i = 1 ，2 ，s 1 记a r c ( f ) 为r 上所有s 一弧的集合通常，我 们将1 - a r c 和a r c 】( f ) 简记为a r c 和a r c ( f ) 令x 表示作用在v ( r ) 上的一个有限群，使得对于任意的z x ，e ( r ) $ = e ( f ) ( 即x 保持r 的邻接关系) r 称为x 一点传递的，如果x 在v ( r ) 上的作 用是传递的( 即对于任意的q i ，q ，y ( r ) ，存在x x 满足q = a j ) 一个点 传递图f 称为是( x ，s ) 一弧一传递的，如果x 在a r c 。( r ) 上诱导的作用是传递的 ( x ，1 ) 一弧一传递图又称为x 一对称图 称r 是x 非本原图，如果v ( r ) 允许一个非平凡的x 不变的划分召，也就是 一个划分召，使得对于任意的b b 及x x ，有1 l b i l y ( r ) l 且b z b 此 时我们可以定义r 关于划分召的商图如为以召为点集的一个图，其邻接关系 为：对于任意的b ，c b ， b ，c e ( r b ) 当且仅当存在r 中的两个点盯b 和 7 - c 使得 几7 - ) e ( r ) 我们考虑r 8 不是空图的情形，此时由【1 】我们有对于 任意的b 舀，b 是f 的一个独立集 称r 是r b 的多重覆盖图，如果对于任意的 b ，c ) e ( f 8 ) 和盯b ，存在 7 c 使得 仃，7 - ) e ( r ) ，否则称r 不是r 启的多重覆盖图特别地，如果上述7 是唯一存在的，就称r 是r 8 的覆盖 当r 是一个有限非空的( x ，2 ) 一弧传递图，8 为其上一个非平凡的x 一不变的 划分，使得b 非空且r 不是如的多重覆盖图时，文献【2 】给出了( r ，x ，召) 当 i r ( c ) nb i = 2 时的一个刻画，这里b 召且c f b ( b ) 这个结果促使我们研 究当i r ( c ) nb i = 3 的情形完成这个工作需要研究度数为4 或7 的( x ，2 ) 一弧一传 递图基于【3 】中的结果，我们将在第一章给出4 度( x ，2 ) 一弧一传递图的一个划分； 同时我们将证明任何一个4 度的( x ，2 ) 一弧传递的非完全图都是准礼边形，这里 佗4 是一个整数对于7 度的( x ，2 ) 一弧传递图，我们将证明可以作为一个 满足条件的r 的商图，当且仅当群p j 竺p s l ( 3 ，2 ) ，这里7 i y ( ) a b s t r a c t ( i nc h i n e s e ) 在第二章中，对于任意一个x 一对称图，我们将给出存在一个( x ，s ) 一弧传递 图r 以为商图，且r 不是的完全覆盖图的充要条件同时，当这条件满足 时，我们将给出一个方法来构造这样一个d 进一步地，对于任何一个( x ，s ) 一弧一传 递图r ，这里s 1 ，我们可以从出发，经过m ( m 是一个自然数) 次这样的构造 过程，我们将得到一个图r ，使得p 兰r 或者r 是r 的一个完全覆盖 关键字：对称图，商图，3 一弧图，双星图 a b s t r a c t a b s t r a c t l e tfb eaf i n i t ex - s y m m e t r i cg r a p hw i t han o n t r i v i a lx - i n v a r i a n tp a r t i t i o n 召o nv ( r ) s u c ht h a tr 8i sac o n n e c t e d ( x ，2 ) 一a r c - t r a n s i t i v eg r a p ha n dri sn o t am u l t i c o v e ro fp b ac h a r a c t e r i z a t i o no f ( p ，x ，g ) w a sg i v e ni n 【2 】2f o rt h ec a s e w h e r ei r ( c ) n b i = 2f o rb 召a n dc f b ( b ) t h i sm o t i v a t e su st oi n v e s t i g a t e t h ec a s ew h e r ei r ( c ) nb i = 3 ，t h a ti s ，r i b ，qi si s o m o r p h i ct oo n eo f3 k 2 ， k s ，3 3 k 2a n d 蚝，3 t h i si n v e s t i g a t i o nr e q u i r e sas t u d yo n ( x ，2 ) 一a r c - t r a n s i t i v e g r a p h so fv a l e n c y 4o r7 b a s e do nt h er e s u l t si n 【3 】，w eg i v eac h a r a c t e r i z a t i o n o ft e t r a v a l e n t ( x ，2 ) 一a r c t r a n s i t i v eg r a p h si nc h a p t e r1 ；a n da sab y p r o d u c t , w ep r o v et h a te v e r yt e t r a v a l e n t ( x ，2 ) - t r a n s i t i v eg r a p hi se i t h e rk 5o ran e a r 佗一g o n a lg r a p h f o rs o m e 佗4 f u r t h e r , w es h o wt h a ta h e p t a v a l e n t ( x ，2 ) 一a r c t r a n s i t i v eg r a p h c a no c c u ra sr bi a n do n l yi f 辟7 竺p s l ( 3 ，2 ) f o r7 y ( ) d e n o t eb y 乡t h es e to ft r i p l e s ( r ，x ，召) ，w h e r eri saf i n i t ex - s 舯e t r i c g r a p ho fv a l e n c yv a l ( p ) 1 ，召i san o n t r i v i a lx i n v a r i a n tp a r t i t i o no fv ( r ) s u c ht h a tf b ，t h eq u o t i e n tg r a p ho fpw i t hr e s p e c tt o 屡，i sn o n e m p t ya n dri s n o tam u l t i c o v e ro fr 召i nc h a p t e r2 ，f o ra n yg i v e nx - s y m m e t r i cg r a p h ，w e w i l lg i v eas u f f i c i e n ta n d n e c e s s a r yc o n d i t i o n f o rt h ee x i s t e n c eo f ( f ，x ，召) 夕， s u c ht h a tr b 竺a n dfi s ( x ，s ) - a r c - t r a n s i t i v ef o rs o m ei n t e g e rs 1 a n di n t h i sc o n d i t i o n , ap r a c t i c a b l em e t h o dw a sg i v e nt oc o n s t r u c ts u c ha n ( x ，s ) 一a r c t r a n s i t i v eg r a p hr m o r e o v e r , f o ra n y ( r ，x ，召) 乡，w ew i l ls h o wt h a tt h e r e e x i s t sa ni n t e g e rm 1 ，s u c ht h a ta f t e rmt i m e so fs u c hc o n s t r u c t i n gp r o c e s s ， w ec a no b t a i na nx s y m m e t r i cg r a p hr f r o mp b ，s u c ht h a te i t h e rf 竺r o r ri sam u l t i c o v e ro ff b m k e yw o r d s ：s y m m e t r i cg r a p h , q u o t i e n tg r a p h ，t h r e e a r cg r a p h , d o u b l e - s t a r g r a p h 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 = 意i z 口矿尸年月r 日 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位芝未芗之芋；j 祛 2 d o7 年与f 日 、 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： r ? 一“”一7 ? j 内部5 年( 最长5 年，可少于5 年) ” ；秘密1 0 年( 最长1 0 年，可少于1 0 年)，! ； 机密2 0 年( 最长2 0 年，可少于2 0 年)“ ， j u 。o ：。“。i 。o 矗 c h a p t e r 1i n t r o d u c t i o na n dn o t a t i o n c h a p t e r1 i n t r o d u c t i o na n dn o t a t i o n i nt h i sp a p e r ，a l lg r a p h sa r ea s s u m e dt ob ef i n i t e ，n o n e m p t y , s i m p l ea n d u n d i r e c t e d t h i sp a p e ri n v o l v e sg r a p h s fp e r m u t a t i o ng r o u p sa n dd e s i g n s ，t h e r e a d e ri sr e f e r r e dt o 【4 - - 6 】r e s p e c t i v e l yf o rt h en o t a t i o na n dt e r m i n o l o g yn o t m e n t i o n e dh e r e l e t b ear e g u l a rg r a p hw i t hv e r t e xs e ty ( ) a n de d g es e te ( ) b yv a l ( ) w ed e n o t et h ev a l e n c yo f f o ra ni n t e g e r8 1a n da n ( 8 + 1 ) - s e q u e n c e 0 f = ( a o ，q l ，q 8 ) o fy ( ) ，s e td 一1 ：= ( o l 8 ，a 8 1 ，s 0 ) ，似i sc a l l e da ns - a r c o fe i f o q ，o q + 1 ) e ( e ) f o ri = 0 ，1 ，s 一1 ，a n d 口i 一1 o q + lf o ri = 1 ，2 ，8 1 a ns a r ca = ( o t 0 ，o r l ，q s ) i sc a h e da ns d i p a t hi fo q 哟f o ri ，j o ，1 ，s ) w i t hi j e v i d e n t l y , 0 fi sa ns a r c ( s d i p a t h ，r e s p e c t i v e l y ) o fei fa n do n l yi f a _ 1i sa ns a r c ( s d i p a t h , r e s p e c t i v e l y ) o fe f o ra n ys d i p a t ho f = ( o t 0 ，口1 ，口s ) o fe ，i d e n t i f y i n go fa n do f 一1g i v e sr i s et oa ns - p a t h a o ，a 1 ，q 8 】o fe d e n o t e b ya r c 。( e ) ( p a t h 8 ( ) ，r e s p e c t i v e l y ) t h es e to fs a r c s ( s - p a t h s ) o f i nt h ec a s e w h e r e8 = 1 ，w eu s ea r ca n da r c ( z ) i np l a c eo f1 - a r ca n da r o ( e ) ，r e s p e c t i v e l y l e txb eag r o u p a c t i n go ny ( ) t h ei n d u c e d a c t i o no fxo nv ( e ) xy ( ) i sd e f i n e db y ( 7 - ，矿) $ = ( 严，o r z ) f o r ( 7 - ，盯) v ( z ) xv ( z ) a n dz x w es a yt h a t x p r e s e r v e s t h ea d j a c e n c yo f i fa r c ( e ) = a r c ( e ) ，f o ra l lx x t h eg r a p h i ss a i dt ob ex v e r t e x - t r a n s i t i v ei fx p r e s e r v e st h ea d j a c e n c yo f a n da c t s t r a n s i t i v e l yo ny ( ) ；a n de i ss a i dt ob e ( x ，8 ) - a r c t r a n s i t i v e ( ( x ，s ) - a r c - r e g u l a r , r e s p e c t i v e l y ) i fi na d d i t i o nt h ei n d u c e da c t i o no fx o na r ( e ) i st r a n s i t i v e ( r e g u l a r , r e s p e c t i v e l y ) f u r t h e r , i ss a i dt ob e ( x ，s ) 一t r a n s i t i v ei f i s ( x ，s ) 一 a r c t r a n s i t i v eb u ti sn o t ( x ，s + 1 ) - a r c - t r a n s i t i v e a n ( x ，1 ) 一a r c - t r a n s i t i v eg r a p h i su s u a l l yc a l l e da nx s y m m e t r i cg r a p h f o r7 - y ( ) ，w ed e n o t eb yx rt h e p o i n t s t a b i l i z e ro f7 - i nx i ti sw e l l - k n o w nt h a t , f o rs 1 ，2 ) ，a nx - v e r t e x - t r a n s i t i v eg r a p h i s ( x ，s ) 一a r c t r a n s i t i v ei fa n do n l yi f 墨i ss t r a n s i t i v eo nt h e 1 c h a p t e r 1i n t r o d u c 廿o na n dn o t a t i o n n e i g h b o r h o o d ( 7 - ) ：=r v ( z ) l ( 7 ，口) a r c ( ) ) o f7 - i n t h er e a d e ri s r e f e r r e dt o 【1 】1f o rb a s i cr e s u l t sa b o u ts y m m e t r i cg r a p h s l e trb eaf i n i t ex - s y m m e t r i cg r a p ha d m i t san o n t r i v i a lx - i n v a r i a n tp a r - t i t i o nbo ny ( r ) ，t h a ti s ，1 l b i v ( r ) a n db 善：= 口zjd 口) 召f o r b ba n dz x ( s u 出ag r a p hi ss a i dt ob ea ni m p r i m i t i v ex - s y n u n e t r i c g r a p h ) t h eq u o t i e n tg r a p hr 8o ff w i t hr e s p e c tt o 召i sd e f i n e dt ob et h eg r a p h w i t hv e r t e xs e tbs u c ht h a t , f o rb ，c 召，bi sa d j a c e n tt oci np bi fa n do 由 i ft h e r ee x i s t ss o m e 口ba d j a c e n tt os o m eu ci nr i ti se a s yt os e et h a t xa c t st r a n s i t i v e l yo nt h ev e r t e xs e ta n do nt h ea r cs e to ff s ，t h a ti s ，tb 毽x s y n x t n e t r i c w ea l w a y sa s s u m et h a tf bh a sa tl e a s to n ee d g e ，w h i c hi m p l i e s t h a te a c hb bi sa ni n d e p e n d e n ts e to fy ( r ) i th a sb e e no b s e r v e di nt h e l i t e r a t u r et h a tt h eq u o t i e n tg r a p h so fa n ( x ，2 ) 一a r c - t r a n s i t i v eg r a p ha r eu s u a h y n o t ( x ，2 ) a r c - t r a n s i t i v e ，a n dt h a ta nx s y m m e t r i cg r a p hw i t ha n ( x ，2 ) 一a r c t r a n s i t i v eq u o t i e n ti t s e l fi sn o tn e c e s s a r i l y ( x ，2 ) 一a r c - t r a n s i t i v e ( f o re x a m p l e ， s e v e r a le x a m p l e sa r eg i v e ni n 【7 ，8 】f o rt h ef i r s ts i t u a t i o n ；a n df o rt h es e c o n d s i t u a t i o n , i ti ss h o w ni n 【3 】t h a te v e r yc o n n e c t e d ( x ，3 ) 一a r c t r a n s i t i v eg r a p hi s aq u o t i e n tg r a p ho fa tl e a s to n ex s y m m e t r i cg r a p hw h i c hi sn o t ( x ，2 ) 一a r c t r a n s i t i v e 。) t h i so b s e r v a t i o ng a v er i s et oas e r i e so fi n t e n s i v e l ys t u d i e so ft h e f o l l o w i n gt w oq u e s t i o n s ( q 1 ) a n d ( q 2 ) 【2 ，9 】b yi n v e s t i g a t i n g7 l o c a l 7s t r u c t u r e s o fi m p r i m i t i v es y m m e t r i cg r a p h sa n dm e i rq u o t i e n tg r a p h s ( q 1 ) w h e n c a l lr 艿b e ( x ，2 ) 一a r c - t r a n s i t i v e ? ( q 2 ) w h a ti n f o r m a t i o no ft h es t r u c t u r eo fr c a nw eo b t a i nf r o ma n ( x ，2 ) 一a r c t r a n s i t i v eq u o t i e n tp bo fr ? f o rb 8a n dd y ( r ) ，w es e tp ( b ) ：= u u br ( u ) ，r b ( b ) ：= c 召i ( b ，g ) a r c ( r s ) a n df b ( o ) ：= g bid r ( c ) ) l e td ( b ) ：= ( b ，r b ( b ) ，i ) d e n o t et h ei n c i d e n c e s t r u c t u r es u c ht h a tr i gf o r 臼b ，c r b ( b ) i fa n do n l yi fc r 8 ( d ) f o ra n yb 磅c r b ( b ) a n d 臼b ，a sri s x - s y m m e t r i c , 口：= i b i ，k ：= l r ( c ) nb i ，r ：= i r 序( d ) ia n db ：= v a l ( f 8 ) a r e i n d e p e n d e n to ft h ec h o i c eo fb a n d0 ，a n dv ( b ) i sa nx b f l a g t r a n s i t i v e1 一 ( v ，k ，r ) d e s i g nw i t hbb l o c k s 【3 ，l e m m a2 1 1 ri ss a i dt ob eam u l t i c o v e ro fr 序 2 c h a p t e r1i n t r o d u c t i o na n dn o t a t i o n i fk = 口f o r ( b ，c ) a r c ( f b ) ，d e n o t eb yr i b ，qt h eb i p a r t i t es u b g r a p ho ff i n d u c e db y ( r ( c ) nb ) u ( r ( b ) nc ) t h e nr b ，qi si n d e p e n d e n to ft h ec h o i c e 0 f ( b ，c ) a r c ( p b ) u p t oi s o m o r p h i s m , a n dx bn a c t st r a n s i t i v e l yo nt h e e d g e so f r i b ，q w i t h o u td o u b t , t h et r i p l e ( f b ，r i b ，q ，d ( b ) ) m i n o r s7 9 l o b a l a n d7 l o c a l i n f o r m a t i o no ft h es t r u c t u r eo fr ，w h i c ha l l o w su st or e c o n s t r u c tfi ns o m e s e n s e t h i sa p p r o a c ht oi m p r i m i t i v es y m m e t r i cg r a p h sh a v er e c e i v e da t t e n t i o n i nt h el i t e r a t u r e g a r d i n e ra n dp r a e g e r 【1 0 】s u g g e s t e dt oa n a l y s et h e s et h r e e c o n f i g u r a t i o n s ，( f ，r i b ，q ，口( b ) ) ，a n dm e yd i s c u s s e dt h ec a s ew h e nri sx l o c a l l yp r i m i t i v e ，t h a ti s ，t h es t a b i l i z e ro fav e r t e x 口v ( r ) i nx a c t sp r i m i t i v e l y o nt h en e i g h b o r h o o dr ( 臼) o ft h ev e r t e xi nr i n 【1 1 ，1 2 】t h e yc o n s i d e r e dt h e c a s ew h e nt h eq u o t i e n tr bi sac o m p l e t eg r a p ha n dt h es e t w i s es t a b i l i s e rx b ( t h es u b g r o u po fxf i x i n gbs e t w i s e ) i s2 - t r a n s i t i v eo nb l i ，p r a e g e ra n dz h o u 【1 3 】p r o v e dt h a t ，i f = 口一1 2 ，t h e nv ( b ) c o n t a i n sn or e p e a t e db l o c k s ( t h a t i s ， t h es u b s e t so fbi n c i d e n tw i t hd i s t i n c tb l o c k so fd ( b ) & r ed i s t i n c t ) i fa n do n l y i ff bi s ( x ，2 ) 一a r c - t r a n s i t i v e , a n df u r t h e rm e yf o u n da l le l e g a n tc o n s t r u c t i o n ( c a l l e dt h e3 - a r cg r a p hc o n s t r u c t i o n ) f o rc o n s t r u c t i n ga l ls u c hg r 叩h sf r o mf b i r a n m a n e s h , p r a e g e ra n dz h o u 【9 1 ，l ua n dz h o u 【3 1s t u d i e dt h ec a s ew h e r et h e q u o t i e n tf bi s ( x ，2 ) - a r c t r a n s i t i v ea n do b t a i n e das e r i e so fi n t e r e s t i n gr e s u l t s i np a r t i c u l a r , l ua n dz h o u 【3 】f o u n dt h e7 s e c o n dt y p e 73 - a r c g r a p hc o n s t r u c t i o n , w h i c hl e dt oac l a s s i f i c a t i o n 【1 4 】o faf a m i l yo fs y m m e t r i cg r a p h s t h er e a d e ri s r e f e r r e dt o 【2 ，1 5 - 1 8 】f o rf u r t h e rm o r ed e v e l o p m e n t si nt h i st o p i c i na n s w e r i n gt h ea b o v et w oq u e s t i o n s ，ar e l a t i v e l ye x p l i c i tc l a s s i f i c a t i o n o f ( r ，x ，舀) h a sb e e ng i v e ni n 【2 】，w h e nf bi sac o n n e c t e d ( x ，2 ) 一a r c - t r a n s i t i v e g r a p hs u c ht h a t2 = k v 一1 t h i sm o t i v a t e d u si nc h a p t e r2t oi n v e s t i g a t e t h ec a s ew h e r ek = 3 ，a n dt h e nw eg i v eac h a r a c t e r i z a t i o nf o rt h i sc a s e f o rag r o u px a c t i n go n as e tva n das u b s e tbo fv ，d e n o t e b yx ( b ) ( x b ， r e s p e c t i v e l y ) t h ep o i n t - w i s e ( s e t - w i s e ，r e s p e c t i v e l y ) s t a b i l i z e ro fb i nx ，a n d b y x 皂t h ep e r m u t a t i o ng r o u pi n d u c e db yx b o nb t h e nx g 笔x b x ( m 3 c h a p t e r 2ac l a s so fs y m m e t r i cg r a p h sw i 小2 - a r c t r a n s i t i v eq u o t i e n t s c h a p t e r2 ac l a s so fs y mm e t r i cg r a p h sw i t h2 - a r c - t r a n s i t i v e q u o t i e n t s 2 1 g r a p h sc o n s t r u c t e df r o mg i v e ng r a p h s h e r e a f t e r , w ed e n o t eb y9t h es e to ft r i p l e s ( r ，x ，b ) s u c ht h a tfi saf i _ n i t ex s y m m e t r i cg r a p hw i t han o n t r i v i a lx - i n v a r i a n tp a r t i t i o n 召o ny ( r ) ， v a l ( r b ) 2a n dfi sn o ta m u l t i c o v e ro ff b ，a n d b y9t h es u b s e to f9s u c h t h a tf 8i sc o n n e c t e da n dxa c t sf a i t h f u l l yo ny ( r ) ，t h a ti s ，n 口e v ( r ) 五= 1 h t h i ss e c t i o n , w ea i mt or e s t a t es e v e r a lg r a p h sc o n s t r u c t e df r o mg i v e ng r a p h s ， a sw e l la ss o l l l eo ft h e i rp r o p e r t i e s ，w h i c ht u r no u tt ob eu s e f u li naf t l r t h e r c h a r a c t e r i z a t i o no f ( p ，x ，b ) 9 t h ef o l l o w i n gt w op r o p o s i t i o n sa r eq u o t e df r o m 【3 】 p r o p o s i t i o n2 1 l e t b eaf i n i t e ( x ，2 ) - a r c - t r a n s i t i v eg r a p hw i t hv a l ( e ) 2 l e t ab eas e l f - p a i r e ds u b s e t 旷a r c 3 ( e ) ，t h a ti s ，0 f 一1 aw h e n e v e ro f a d e f i n e 】：= 】( ，a ) t ob et h eg r a p hw i t hv e r t e xs e tp a t h 2 ( e ) a n de d g e s e t i r ( d ) n bnr ( c ) i ：= 入2 ，s oqi sap r o p e rr e f i n e m e n to f 召i np a r t i c u l a r , t h ep a i r ( 召，q ) g i v e sa nx i n v a r i a n tp a r t i t i o n 召o fv ( r q ) 5 c h a p t e r2a c l a s so fs y m m e t r i c g r a p h sw i t h2 - a r c - t r a n s i t i v eq u o t i e n t s c o n s i d e rt h e q u o t i e n tg r a p h ( r q ) 廖o fr qw i t hr e s p e c tt o 廖f o ra n y2 - p a t h 【d 一，b 一，翻o f ( f q ) aa n da n y 石v ( r q ) ，w eh a v ei ( r q ) 廖( 6 ) l = 2a n di r q ( d ) n j yn r q ( d ) j = 1 i tf o l l o w sf r o m ( a ) t h a tr q 竺】( ( r q ) 廖，厶) ，w h e r e 厶= ( o ，雪( 石) ，豆 ) ，d ) i ( c ，b ( 臼) ，b ( u ) ，d ) ) m o r e o v e r , i ti se a s i l ys h o w nt h a t8 一召，bhb i sa ni s o m o r p h i s mf r o m ( p q ) a t or 8 t h e r e f o r e , r q 笺】( ( r q ) 廖，厶) 兰】( r 8 ，) i f o raf i n i t ex s y m m e t r i cg r a p hew i t hv a l e n c yn ol e s st h a nt h r e e ，l e tj ( e ) b et h es e to fp a i r s ( 【丁1 ，丁，死 ， 盯1 ，盯，仃2 】) o f2 - p a t h so f s u c ht h a to r e ( r ) n ，吃】，r e ( a ) 1 ，c r 2 ) as u b s e ta o fj ( s ) i ss a i dt ob es e l f - p a i r e di f ( 丁1 ，7 - ，死 ， 0 1 ，盯，盯2 】) aa l w a y si m p l i e st h a t ( p 1 ，正a r 2 】，【n ，7 ，死】) a p r o p o s i t i o n2 3 l e te b ea f i n i t e ( x ，2 ) - a r c t r a n s i t i v eg r a p hw i t hv a l ( e ) 3a n d ! 甜ab eas e l f - p a i r e dx o r b i to nj ( ) d e f i n ea g r a p h 皿：= 皿( ，a ) w i t hv e r t e xs e t p a t h 2 ( e ) s u c ht h a tt w o2 - p a t h s 可，oa r ea d j a c e n ti fa n do n l yi f ( 可，盯) a t h e n 皿 i sx - s y m m e t r i ca n dpf san o n t r i v i a lx i n v a r i a n tp a r t i t i o no fy ( 皿) w i t h 兰皿p ， w h e r epi sd e f i n e da si np ? 叩o s i t i o n2 1 w en o w q u o t ear e s u l ta b o u t3 - a r cg r a p h s 【1 3 1 p r o p o s i t i o n 2 4 l e teb ea f i n i t e ( x ，2 ) - a r c - t r a n s i t i v eg r a p hw i t hv a l ( e ) 3a n d 胁b eas e l f - p a i r e dx - o r b i to na r c s ( e ) t h e3 - a r cg r a p h 三：= s ( s ，a ) w i t hr e s p e c t 幻ai sd e f i n e dt ob et h eg r a p hw i t hv e r t e xs e ta r c ( e ) s u c ht h a tt w oa r c s ( 丁，7 1 ) a n d ( 仃，o 1 ) o f ea r ea d j a c e n ti n 三i f a n do n l yi f ( t 1 ，丁，仃，0 - 1 ) a t h e n ( 三，x ，a ) 9a n d