共查询到19条相似文献,搜索用时 187 毫秒
1.
高敬振 《高校应用数学学报(A辑)》1992,7(2):315-316
设H为一图.H中由m个点组成的独立集和由m个点组成的割集分别称为m-独立集和m-割集,而经过v∈V(H)的圈v-圈.设D为H的子图,测|D|和H-D分别表示|V(D)|(D的阶)和H-V(D).称H是无爪的,如果它不含K_(1,3)作为导出子图.称H是m-路连通的(m≥1),如果|H|≥2,H的任一对点都由长度≥m的路相联.称只有一个点的图为0-路连通的.H中的路R是一dominating路,如果R是Hamilton的,或者V(H-R)是一独立点集.对H的子图A和D,令 相似文献
2.
3.
徐军 《数学的实践与认识》2010,40(24)
一个图G称为(X,Y)-free图,如果G不含同构于子图X和Y的导出子图.本文证明了X=K_(1,3)、Y∈{D,W,B}的3-连通(X,Y)-free图是Hamiltonian-连通的. 相似文献
4.
5.
6.
图G=(V,E)的每个顶点控制它的闭邻域的每个顶点.S是一个顶点子集合,如果G的每一个顶点至少被S中的两个顶点控制,则称S是G的一个双控制集.把双控制集的最小基数称为双控制数,记为dd(G).本文探讨了双控制数和其它控制参数的一些新关系,推广了[1]的一些结果.并且给出了双控制数的Nordhaus-Gaddum类型的结果. 相似文献
7.
本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立. 相似文献
8.
可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$.若图中任意距离为2的两点$u,v$满足$J(u,v)\neq \emptyset$,则称该图为半无爪图.令$\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$为$G$中含有$k$个点的独立集\},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{3}(G)\geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{2}(G)\geq \frac{2({n-2})}{3}$,则该图为可迹图. 相似文献
9.
本文证明了下列结论:设G是p阶3-连通无爪简单图。若对于G中任意3个顶点的独立集{x1,x2,x3},有 d(x1)+d(x2)+d(x3)≥p+1 则G是Hamilton-连通图。 相似文献
10.
设tγ(G)为G的全控制数.证明了:(1)对广义θ-图G,tγ(G)≤α(G) 1;(2)对任意k-正则无爪图G,k≥3,有tγ(G)≤α(G).这里α(G)表示G的匹配数.作为结果(2)的推论,对k-正则无爪图(k≥3),证明了Favaron猜想是成立的.即对最小度不小于3的简单图,有tγ(G)≤12 V(G).此外,举例说明了当图的最小度不超过2时,对一般图而言,匹配数与全控制数不可比较. 相似文献
11.
图的倍图与补倍图 总被引:7,自引:0,他引:7
计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题.对简单图C,如果V(D(G)):V(G)∪V(G′)E(D(G))=E(C)∪E(C″)U{vivj′|vi∈V(G),Vj′∈V(G′)且vivj∈E(G))那么,称D(C)是C的倍图,如果V(D(G))=V(C)∪V(G′),E(D(C)):E(C)∪E(G′)∪{vivj′}vi∈V(G),vj′∈V(G’)and vivj∈(G)),称D(C)是G的补倍图,这里G′是G的拷贝.本文研究了D(G)和D的色数,边色数,欧拉性,哈密顿性和提出了D(G) 的边色数是D(G)的最大度等公开问题. 相似文献
12.
A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted Tc(G),is the minimum cardinality of a clique- transversal set in G.In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound.Also,we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound. 相似文献
13.
14.
15.
一个有向图D的有向Pk-路图Pk(D)是通过把D中的所有有向k长路作为点集;两点u= x1x2…xk+1,v=y1y2…yk+1之间有弧uv当xi=yi-1,i=2,3,…,k+1.明显地,当k=1时Pk(D)就是通常的有向线图L(D).在[1,2]中,P2-路图得到完整刻画.在[3]中,Broersma等人研究了有向... 相似文献
16.
本文证明了极大饱和图D(n,k)的一个极值性质:在与D(n,k)具有相同度序 所有图中,唯有D(n,k)含有最少的K3子图,并由此推出,在几乎正则图的范围内,k个完全图之并及完全k部多分图均是圈唯一的。本文还用图谱方法,证明了完全二分图Km,n的圈唯一性。 相似文献
17.
二面体群D_(2n)的4度正规Cayley图 总被引:4,自引:0,他引:4
设G是有限群,S是G的不包含单位元1的非空子集.定义群G关于S的 Cayley(有向)图X=Cay(G,S)如下:V(x)=G,E(X)={(g,sg)|g∈G,s∈S}. Cayley图X=Cay(G,S)称为正规的如果R(G)在它的全自同构群中正规.图X称为1-正则的如果它的全自同构群在它的弧集上正则作用.本文对二面体群D2n以Z22 为点稳定子的4度正规Cayley图进行了分类. 相似文献
18.
A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger than β have different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented. 相似文献