包含子图K4的无割点次极大图的唯一性-论文.pdf

《包含子图K4的无割点次极大图的唯一性-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第43卷第10期数学的实践与认识V_o1．43．NO．102013年5月MATHEMATICSINPRACTICEANDTHE0RYMay,2013·包含子图肠的无割点次极大图的唯一性林跃峰(漳州城市职业学院经济管理系，福建漳州363000)摘要：研究次极大图(即链环分支数等于基圈数的连通平图)的唯一性．证明了无割点且包含子图的连通平图G是次极大图当且仅当G同构于，并刻画了包含子图4的次极大图的结构．关键词：次极大图；Ka；链环分支数；基圈数；唯一性；结构设G是一个图．约定p(G)，q(a)，k(a)和(G)分别是图G的顶点数，边数，连通分支数和

2、秩．图G的基圈数定义为n(a)=q(a)一p(a)+(G)．设：rG(x，Y)是图G的Tutte多项式【1]．设(G)：log2(I(一1，-1)1)+k(a)是图G的链环分支数．当G是平图时，(G)恰好是由图G通过中间图构造所对应的链环的连通分支数[2-3】．(G)=1的连通平图四十多年前已研究【4Jj文[5]研究了其构造．文[6】定义了极大图，即U(a)=n(G)+1的连通平图．文【7]定义了次极大图，即(G)=他(G)的连通平图，并证明了在顶点的最小度(G)=3的条件限制下的连通平图G是次极大图当且仅当GK4．(见文[7】定理3．2和推论3

3、．3)．关于平图对应的链环的分支数有关的工作，见文[8—10]．本文研究包含子图K4的无顶点的最小度(G)：3的条件限制的次极大图．证明包含子图甄的无割点连通平图G是次极大图当且仅当G同构于完全图4，并刻画包含子图4的次极大图的结构．1一些已知的结论我们需要下面的引理1．1—1．6(分别见文[6】的定理3．4，引理3．1，引理2．3，引理4．3，引理4．2和引理4．4)和定理1．7(见文[7]定理3．2和推论3．3)．引理1．1设G是连通平图，则1(G)min{r(G)+1，n(G)+1)．引理1．2设G是平图，V∈V(Gi)(：1，2)，G是粘

4、合两顶点Vl和V2所成的平图．则(G)=u(G1)+u(G2)一1．特别地，1)若G1=Cl，贝0(G)=(G2)；2)若e是平图G的割边，则(G／e)=(G)．引理1．3设G是平图．收稿日期：2012．10—14资助项目：福建省教育厅A类科技项目(JAl1332)10期林跃峰：包含子图的无割点次极大图的唯一性1571)若e和．厂是G的一对序列边，则,(G／~／y)：(G)；2)若e和．厂是G的一对平行边，则(G—e一，)=(G)．引理1．4设G是一个连通平图．若(G)3，则(G)扎(G)．引理1．5设G是一个连通平图，e和．厂是G的一对平行边．

5、若G—e一，连通，则(G)n(C)一1．‘●引理1．6设Gt是连通平图，Vi∈v(at)(=1，2)，G是粘合两顶点1和V2所成的平图．则G是极大图当且仅当Gi(=1，2)都是极大图．一般地，若G1，G2，⋯，G是G的块，则G是极大图当且仅当G1，G2，⋯，G都是极大图．定理1．7设G是连通平图，(G)=3，则G是次极大图当且仅当GK4．2几个引理本节我们证明几个有关极大图和次极大图的判定的引理．引理2．1设Gi是连通平图，Vi∈(G)(=1，2)，G是粘合两顶点V1和V2所成的平图．则G是次极大图当且仅当G和G2一个是次极大图，另一个是极大图．

6、证易知n(G)=n(G1)+佗(G2)，由引理1．2，有(G)：(G1)+(G2)一1．故G是次极大图当且仅当(G1)+(G2)=佗(G1)+n(G2)+1．由引理1I1，知G是次极大图当且仅当G1和G2一个是次极大图，另一个是极大图．口一般地，若G1，G2，⋯，是G的块，则G是次极大图当且仅当G1，G2，⋯，G恰有一个块是次极大图而其余的块都是极大图．引理2．2设G是连通平图．若dG(v)=2且V邻接于两个不同的顶点和Y．则1)G是极大图当且仅当al(v，x)／(v，Y)是极大图．2)G是次极大图当且仅当a／(v，)／(”，Y)是次极大图．证因

7、G是连通平图，da(v)=2且邻接于两个不同的顶点X和Y，则G／(，)／(，Y)是连通平图，且n(G／(，)／(，))=佗(G)，由引理1．3(1)知(G／(，x)／(v，))：(G)．故1)G是极大图当且仅当a／(v，)／(，Y)是极大图．2)G是次极大图当且仅当G／(，x)／(v，Y)是次极大图．口引理2．3设G是一个连通平图，若(G)4，或(G)=3且G仅有一个度为3的顶点，贝0(G)

8、)．若(G)=3且G仅有一个度为3的顶点，贝0n(C)=q(C)一p(c)+1—3+—4—(p(G—)一-1)一p(a)+1p(c)+，