共查询到20条相似文献,搜索用时 125 毫秒
1.
徐利民 《淮南职业技术学院学报》2011,11(2)
计数问题是图论研究的一个课题,图的一些特殊子图的计数确定了图的着色性;在这里使用组合数学的方法,估计了二部图K(u,v)-A和三部图K(n+a1,n+a2,n+a3)-A的三角形子图和没有弦的四边形子图的计数,在三部图中比较了这些特殊子图的计数. 相似文献
2.
研究了完全二部图及其局部边迁移图的边优美性.主要结果有:当(m,n)=1时,奇阶完全二部图K(m,n)为边优美图的充要条件是m+n|mn+1. 相似文献
3.
给出了生成子图的定义;证明了生成子图的计数定理和构造定理;提出了生成树的计数方法和构造方法;介绍了完全二分图K3,4的生成子图的计数和构造. 相似文献
4.
高炜 《昆明师范高等专科学校学报》2012,(6):5-9
若删除G中任意一个独立集后得到的图依然是分数(g,f,m)-消去图,则称G为分数ID-(g,f,m)-消去图.将若干个关于分数消去图邻域并条件的结论推广到分数ID-消去图,证明了如下两个结论:1)阶为n的图G满足n≥12k+6m-11,6(G)≥n/3+k+m,且/NG(x)UG(y)/≥2n/3对G中任意一对不相邻的顶点x,y都成立,则G是分数ID-(k,m)-消去图;2)若δ(G)≥(an/2a+b)+(b2(i-1)/a+2m,n〉((2a+b)[i(a+b)+2m-2])/a,且/NG(x1)u…uNG(x1)/≥(a+b)n/2a+b,对V(G)的所有独立集{x1,……,xi}都成立.则G是分数ID-(g,f,m)-消去图. 相似文献
5.
设G是一个简单图,G^--+,G^-+-是G的变换图.在这篇文章中,证明了对于给定的一个图G,(1)G^--+是平面图当且仅当n≤3或G同构于2K1+K2,K1+K1,2,K1,3或K1+C3;(2)G^-+-是平面图当且仅当n≤4且G不同构于K4-e. 相似文献
6.
7.
研究了二部图与一些图的笛卡尔乘积图的平衡指标集,得到 K1,m□K1,m ,K2,m□K2,m ,Kn,n+1□Pn+1,Km,n□Ct的平衡指标集的准确值。 相似文献
8.
探讨一个六阶图与路的联图的交叉数.利用完全二部图k6,n的交叉数结果,证明了该六阶图与路的联图的交叉数为:Z(6,n)+n+1,n≥2. 相似文献
9.
多部图λkn(g)的G-设计,G为有1条悬边的4长圈 总被引:1,自引:0,他引:1
舒伟 《海南师范学院学报》2006,19(4):296-300
设λkn(g)是一个入重完全n部图,G为一个不带孤立点的简单图,一个λkn(g),G)-设计是将λkn(g)划分成边互不相交的子图,使得每一个子图都和G同构.在此基础上讨论了G为有1条悬边4长圈时多重完全多部图的G-设计的存在性,并给出其存在谱. 相似文献
10.
摘要:目前已经确定的两个图的联图的交叉数结果比较少,为此讨论了五阶图G18分别与nK1,Pn的联图的交叉数,得到了cr(G18+nK1)=Z(5,n)+n+[n/2],n≥i;cr(G18+Pn)=Z(5,n)+n+[n+2,n≥2.其中nK1是n个孤立点构成的图,只是Pn个点的路. 相似文献
11.
边冠图G□H是由图G和H合成的图,其中使图G的每条边的两端点与图H的一个拷贝的所有顶点相连.如果图G的边集合可以分解为若干个边不相交的子图H,那么称G有子图H的分解,当H是P3或P4时,就称G有{P3,P4}分解.本文讨论了一些边冠图的{P3,P4}分解问题,即:边冠图Pm□Pn、Pm□Cn、Cm□Pn及Cm□Cn存在{P3,P4}分解. 相似文献
12.
图划分具有广泛的应用,主要应用于VLSI(大规模集成电路)设计,并行计算,数据挖掘和图像分割等领域,因此得到了国内外学者的普遍关注和大量研究。由于图划分是NP-完全问题,因此本文在一般图划分问题基础上提出了特殊点割集及点分割数的概念,主要应用图的连通性原理分析,给出路、圈、扇图、轮图及完全二部图及联图P n,C n,F1n,W n,K m,n,m i=1ΣK n i等的点分割数,并分析讨论了完全图Kn删除一个独立边集后,其点分割数的变化情况。 相似文献
13.
讨论了一类2-连通无爪图的最长圈,若G是2-连通的无爪图,C是G的最长圈,G的阶为n,并且ξ(G)<1/2λ(G),则C(G)≥2/3(n+6). 相似文献
14.
研究了完全二部图及其局部边迁移图的边优美性.主要结果有:当(m,n)=1时,奇阶完全二部图K_(m,n)为边优美图的充要条件是m+n|mn+1. 相似文献
15.
16.
若μ(G,x)=μ(H,x),则称G与H是匹配等价的,记为G~H.若G~H,可导出G与H是同构的,则称图G是匹配唯一的.在本文中,给出了许多完全图的删边子图及其补图是匹配唯一的充要条件. 相似文献
17.
林启法 《宁德师专学报(自然科学版)》2010,22(3):233-234,242
Hamilton图是图论中重要的一类特殊图.主要证明了两个图的联图是Hamilton图,从而进一步证明了n个图的联图也是Hamilton图. 相似文献
18.
研究非连通图CmUPn的优美性,证明了C2n+1UPn.C4aU2n+2,C4mUP2n+3,C4a-1UP2n+2,C4m-1UP2n+1,C8n-1UP2m+3,C8mP2m+3,C8m+1P4m。是优美图,还证明了一类细分图是优美图.得到了相应的优美标号. 相似文献
19.
20.
Given a graph G,a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and |C|≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as TC (G), is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K (G), is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F={G|K(G) is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus TC (G)/|G|≤1/2 for all G ∈ F. 相似文献