共查询到20条相似文献,搜索用时 62 毫秒
1.
一个图G(V,E)的控制数γ(G)是V的这样一个子集S的最小基数,使得G中每一个顶点或者在S中或者和S中的一些顶点邻接。本文讨论了控制数为2的n阶简单连通图的邻接谱半径下界,给出了谱半径达到最小时的极图。 相似文献
2.
薛秀谦 《山东大学学报(理学版)》1994,(1)
仙人掌图是一个简单连通图,其每个块或者是一条边,或者是一个圈.如果两个国的邻城复形的各阶同调群分别同构,则称这两个图是邻城同调的.本文研究了仙人掌的邻域同调群的性质,给出了仙人掌图邻城同调分类的一个充要条件. 相似文献
3.
折叠超立方体是最受关注的网络模型之一.设e是图G的一条边, 如果从图G中删掉以e为中心的双星子图,则称e"倒戈".设S为一个边集, 如果S中的边全部倒戈, 若剩下的子图或者不连通, 或者是一个孤立点, 或者是空集, 则称S为G的割边策略.G的最小割边策略所含的边数为边邻域连通度.该文主要证明了折叠超立方体FQn的边邻域连通度为n. 相似文献
4.
主要研究了星图网络Sn的定向图.证明了如下结论:对于非负整数a和b,若存在满足每个顶点的入度或者是a或者是b的一个Sn的定向图,则存在非负整数s和t满足方程s+t=n!和as+bt=(n-1)/2.进一步,对于满足特定条件的非负整数a,b和n,存在Sn的定向图使得每个顶点的入度或者是a或者是b. 相似文献
5.
6.
给定图G,Ramsey数R(G)是最小的正整数N,满足对完全图K_N的边任意红蓝着色,则或者存在红色子图G或者存在蓝色子图G.扫帚图B_(k,m)是将星图K_(1,k)的中心点与路Pm的一个端点黏成一个点得到的树图.由此得到,当k为大于1的正整数时,R(B_(k,2k-1))=4k-2且R(B_(k,4))=2k+3. 相似文献
7.
设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。 相似文献
8.
9.
李永洁 《华中科技大学学报(自然科学版)》1981,(4)
本文证明了:每个n-棱-连通图G,或者含有一个去掉后G仍为n-棱-连通的顶点,或者含有一个n度顶点.同时,对文献[1]有所改进与发展. 相似文献
10.
一个含有生成闭迹的图称为超欧拉图。设G是n阶3-边连通图,若对任意G的边数为3的最小边割E都满足G-E遥每一连通分支的阶至少为(n-1)/10,则或者G是超欧拉图,或者G可收缩为G‘=Petersen图,且G‘的每个顶点在G中的原像是G的一个可折叠子图,其顶点数至少是(n-1)/10。 相似文献
11.
史天治 《长春师范学院学报》2006,(10)
该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图。两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系。面是平面图区别于非平面图的本质特征。同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的。任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过D—过程画出。平面图与其对偶图互为对偶。显平面图与其隐对偶图合称为相伴对偶图。 相似文献
12.
整和图理论研究的是图的一种标号方法,从实用的角度看,整和图标号可用作图的压缩表示,即表示图的数据结构,可作为图的一种定义及存储方式.笔者采用顺序标号法分别给出贝壳图MS{4n}、MS{5n}的整和标号,从而进一步推广并证明了所有贝壳图MS{mn}(m≥3,n≥2)都是整和图. 相似文献
13.
14.
三部完全图为H_2-cordial图的充要条件 总被引:1,自引:0,他引:1
堵根民 《内蒙古大学学报(自然科学版)》2009,40(2)
完全图、轮和二部完全图的H2-cordial问题已得到解决.借助于二部完全图边标号的矩阵表示法,构造出三部完全图边标号矩阵表示法,给出了三部完全图为H2-cordial图的充分必要条件. 相似文献
15.
文中对限制颜色总数的图作了进一步的研究.运用唯一列表染色的定义找出了非唯一2-列表可染图K5和K3,3,并运用独立集的定义给出了唯一3-列表可染图的一个充要条件:设G是2-连通的图,则G是唯一3-列表可染的当且仅当存在G的一独立集W,使得G\W既不是完全图,也不是完全二分图,也不是圈. 相似文献
16.
谱图理论的一个主要问题是研究图的结构性质如何由图的谱性质反映.割点数是图的重要结构参数,讨论了单圈图的割点数和谱半径之间的联系.在刻画了给定割点数的单圈图中具有最大谱半径图的结构基础上,延续这一讨论,刻画了在某些情形下,给定割点数的单圈图中具有第二大谱半径的图的结构. 相似文献
17.
高润霞 《安庆师范学院学报(自然科学版)》2012,18(4):22-25
设Y是一个图集合,若对于Y中的所有图中,图G的最小特征值可以达到最小,则称G是集合Y中最小特征值的极小图。本文刻画了直径为3的n阶连通图最小特征值及其极小图。 相似文献
18.
A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph. In this paper, we show some necessary
conditions that a 2-walk (a, b)-linear graph must obey. Using these conditions and some basic theorems in graph theory, we characterize all 2-walk linear
graphs with small cyclic graphs without pendants. The results are given in sort on unicyclic, bicyclic, tricyclic graphs. 相似文献
19.
20.
Lenhard Ng(1997)给出k-可序(k-ordered)哈密尔顿图的定义,并证明了每一个(k 1)-Hamilton-连通图都是k-可序哈密尔顿图.Faudree J R(2000)将k-可序哈密尔顿图的定义改进为k-可序图.根据Lenhard Ng提出的开问题:是否存在3-正则4-可序哈密尔顿图的无限类,以及Faudree J R给出的可序图的定义.构造了3-正则4-可序图的无限类. 相似文献