Harary图的k-偶匹配可扩性     

惠志昊  杨雨 《洛阳师范学院学报》2011,30(8):17-19

设图G是一简单的且有完美匹配的连通图.称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(V(G)-2)2)的偶匹配M都可以扩充为G的一个完美匹配.本文主要刻画了Harary图的k-偶匹配可扩性:对于任意的n,如果r(r>4)是偶数,那么Hr,2n是2-偶匹配可扩的等等.  相似文献   

二分图为k-消去图的2个条件     

杨宏晨  薛秀谦 《东南大学学报》2003,19(2)

图G的一个k 正则支撑子图称为G的k 因子 .若对G的任一边e ,图G总存在一个k 因子不含e ,则称G是k 消去图 .若图G存在一个划分 (X ,Y)使得G的每条边的端点分别在X和Y中 ,则称G =(X ,Y)为二分图 .证明了二分图G =(X ,Y)且X =Y是k 消去图的充分必要条件是kS≤r1+2r2 +… +k(rk+… +rΔ) -ε(S)对所有S X成立 .并由此给出二分图是k 消去图的一个邻集充分条件 .  相似文献   

一类特殊图关于Merrifield-Simmons指标的排序     

王燕凤  马宁 《宁夏师范学院学报》2014,(6)

以m阶圈Cm与n+1阶扇Fn+1为组成部分,利用两次单点重合连接方式定义了一种特殊平面图类CFk(m,n+1),并研究了该图类关于Merrifield-Simmons指标的排序问题,得到了不同k值图类CFk(m,n+1)关于Merrifield-Simmons指标的排序结果.  相似文献   

关于临界n_连通图的一些性质     

林育青 《韩山师范学院学报》1992,(3)

本文给出了临界n_连通图的充要条件,临界n_连通图是第一类图和临界n_连通图(v<2n+1)是临界n_边连通图等性质.  相似文献   

广义Petersen图的再推广          下载免费PDF全文

庄容坤 《惠州学院学报》1993,13(3):21-22

本文将广义 Petersen 图推广到更广泛的形式 P(n,r,k),并证明:除 P(5,1,2)外其它的 P(n,r,k)均是第一类的。  相似文献   

关于直径为2-临界图的Murty-Simon猜想     

徐文琴 《廊坊师范学院学报(自然科学版)》2021,(2):5-9

称图G是直径为2-临界图,如果G的直径是2,任意删掉一条边这个图的直径都会增加.一个非常著名的猜想,称为Murty-Simon猜想,指出对于任意有n个点的直径为2-临界图,它的边数最多为[n2/4」,且为完全二部图K[n/2],[n/2]时可以取到边数的上界.一个图称为是3t-临界图,简记为3tEC,如果它的全控制数是...  相似文献   

两类图的平衡性     

《嘉应学院学报》2016,(2):11-15

研究了图P_n~3和毛毛虫树T(k_1,k_2,…,kn)的平衡性,得到了图P_n~3在n=6k,6k+1,6k+4,6k+5时是平衡图,毛毛虫树T(k_1,k_2,…,kn)是平衡图等结论.  相似文献   

导出匹配可扩图的韧度     

周素静  王峥  李静 《天中学刊》2010,25(2):1-3

如果图G的每一个导出匹配都包含在图G的一个完美匹配中,则称图G是导出匹配可扩的.用T(G)表示图G的韧度,文章的主要结论是:设G是有2n(n≥3)个顶点的非完全图,如果G是导出匹配可扩的,则2/(n-1) ≤T (G) ≤n-1;对于任意满足2/(n-1) ≤p/q≤n-1,p+q≤2n,1≤q≤n-1的数p/q,都有韧度为p/q的导出匹配可扩图.  相似文献   

一种构造k—色临界图的方法     

李雪峰 《河北职业技术学院学报》2009,(3)

图G的色数χ(G)是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有χ(H)<χ(G)=k,则称G是k—色临界的,因此可以给出一种构造k—色临界图的方法。  相似文献   

双圈图的解析     

卢晶 《商洛学院学报》2011,25(2):46-50

得到一类特殊双圈图的解析值和两种关于b(G)相等的图类。利用数学归纳法和分类讨论的方法,得到双圈图的紧的下界,证明了在所有阶为n的双圈图中,图△n*-6取得最小的a(G)和b(G),其中图△n*-6表示路Pn-6的两个端点各与一个k3相连所得双圈图。  相似文献   

P-图与它的结构     

孔淑霞 《德州学院学报》2014,(2):51-53,66

利用P-集合,提出P-图,P-图是由内P-图GF-与外P-图GF构成的图对;或者(GF-,GF)是P-图,P-图具有动态特性.给出P-图的结构,给出P-图与普通图的关系;在一定条件下,P-图能回到普通图的"原点".P-图是普通图论中的一个新的研究方向与研究分支.  相似文献   

A''da''m-自补有向循环图     

孙水玲 《广东技术师范学院学报》2008,(6)

A'da'm自补有向循环图是循环图中很独特的一类,有很好应用前景,特别在网络时代的今天,A'da'm自补有向循环图更具它独特的魅力。但是,A'da'm自补有向循环图一般结构很难给出,本文给出了三类自补有向循环图。  相似文献   

一类非连通图Cn^（3）∪Fm,4的优美性     

张红霞 《运城学院学报》2011,(5):16-20

1980年C．Delorme等人证实了Cn^（3）是优美图,本文主要对C4k^（3）∪Fm,4和C4k＋1^（3）∪Fm,4以及C4k＋3^（3）∪Fm,4的优美性进行研究,证明了它们是优美的。  相似文献   

项链图N(m,n)的超边幻和标号及其算法     

刘家保  邹婷  陆一南 《嘉应学院学报》2013,31(2):19-23

研究了一类项链图的超边幻和标号问题,通过建立数学模型,设计了项链图类超边幻和标号的求解算法,并结合实例严格证明了项链图是一类新的超边幻和图等结论.  相似文献   

一种构造k-色临界图的方法     

李雪峰 《廊坊师范学院学报(自然科学版)》2009,9(3):7-8

图G的色数Х（G）是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有Х（H）〈Х（G）=k,则称G是k-色临界的,因此可以给出一种构造k-色临界图的方法。  相似文献   

一类偶圈广义冠图nC_4的超边幻和标号     

刘家保  陈中华  钱金龙  朱秀祥 《嘉应学院学报》2013,(8):10-14

研究了偶圈广义冠图1C4和2C4的超边幻和标号算法,得出了这些图类都是超边幻和图,并给出了相应的数学证明.在此基础上,给出了对于n∈N*,nC4是具有边幻常数K=8n+12的超边幻和图,本文的结果推广了现有的关于超边幻和标号的结论.  相似文献   

范条件图的上可嵌入性   总被引：3，自引：0，他引：3  

吴向群  任韩 《泉州师范学院学报》2004,22(2):44-46

关于图的上可嵌入性，刘彦佩和Nebseky分别给出不同形式的充要条件，黄元秋从另一相反角度出发，提供了一个关于不是上可嵌入图的充要条件，章利用关于不是上可嵌入图的充要条件，证明了范条件图是上可嵌入的。  相似文献   

关于直径为5的图脆弱度的一个注记(Ⅱ)     

许承德 《上海大学学报(英文版)》2005,9(4)

The line persistence of a graph G, p1 (G) is the minimum number of lines which must be removed to increase the diameter of G. In Ref. [ 7 ] ( J. Shanghai Univ., 2003,7(4) :352-357), we gave a characterization of graphs of diameter five with P1 ( G ) ≥ 2. In this paper we will show that each of the 8 special graphs Xi ( i = 1,2,3,4,5,6,7,8 ) listed in condition (2) of Theorem 1 in Ref. [ 7 ] can not be deleted. Therefore the results we obtained in Ref. [ 7 ] can not in general be improved.  相似文献   

3＿线图的完美性     

林育青 《韩山师范学院学报》1997,18(2):27-29

本文给出了3＿线图含有奇洞的充要条件，从而使3＿线图的完美图猜想得到彻底解决，同时，本文还给出完美3＿线圈是k点染色的充要条件及3＿线图是连通的充要条件等一些结论。  相似文献   

正则图的剖分图的秩     

何梅芝 《娄底师专学报》2006,(3):21-23

讨论几类正则图的剖分图的邻接矩阵的秩。主要有：圈，路，完全图，完全二部图和多部图，度为3与4的循环图。  相似文献