共查询到20条相似文献,搜索用时 375 毫秒
1.
包装{(p,p-1),(p,p)}图对和 Slater 问题 总被引:2,自引:0,他引:2
设 G 是一个简单无向图.V(G),E(G)分别表示 G 的顶点集和边集.(?)表示 G 的补图.我们以 S_(?) 表示 n 1阶星图 k_(1,n-1).称 G 是(p,p—k)图,如果|E(G)|=|V(G)|—k.称|V(G)|为图 G 的阶.设 G_1,G_2是同阶图,(?)_1是 V(G_1)到 V(G_2)的一个双射,(?)_2是 V(G_2)上的一个置换,我们用(?)_2(?)_1表示 V(G_1)到 V(G_2)的双射,其作用为 相似文献
2.
非连通图G_1uG_2及G_1uG_2uK_2的优美性 总被引:1,自引:0,他引:1
将k-优美图的概念进行了推广,引入了k~l 优美图及标号间距的概念,并以此为基础, 分别推出了一般情形下判定非连通图G_1 ∪G_2及G_1 ∪G_2 ∪K_2是优美图的两个充分条件;同时得出了图(C_3 ∨(?)_n)∪St(m)∪K_2是优美图,其中k、l 为自然数,l相似文献
3.
图G的圈点连通度,记为κ_c(G),是所有圈点割中最小的数目,其中每个圈点割S满足G-S不连通且至少它的两个分支含圈.这篇文章中给出了两个连通图的笛卡尔乘积的圈点连通度:(1)如果G_1≌K_m且G_2≌K_n,则κ_c(G_1×G_2)=min{3m+n-6,m+3n-6},其中m+n≥8,m≥n+2,或n≥m+2,且κ_c(G_1×G_2)=2m+2n-8,其中m+n≥8,m=n,或n=m+1,或m=n+11;(2)如果G_1≌K_m(m≥3)且G_2■K_n,则min{3m+κ(G_2)-4,m+3κ(G_2)-3,2m+2κ(G_2)-4}≤κ_c(G_1×G_2)≤mκ(G2);(3)如果G_1■K_m,K_(1,m-1)且G_2■K_n,K_(1,n-1),其中m≥4,n≥4,则min{3κ(G_1)+κ(G_2)-1,κ(G_1)+3κ(G_2)-1,2_κ(G_1)+2_κ(G_2)-2}≤κ_c(G_1×G_2)≤min{mκ(G_2),nκ(G_1),2m+2n-8}. 相似文献
4.
本文仅考虑有限、无向、无环的简单图.P(G,λ)表示图 G 的色多项式.如果从P(H,λ)=P(G,λ)可以推出图 H 和 G 同构,则称 G 是色唯一的.设 G 是一个顶点数不超过 n 的图,用 K_n—E(G)表示从完全图 K_n 中删去一个和G 同构的子图的所有边而得到的图.关于 K_n—E(G)型图中的色唯一图的研究已有不少结果,参见[1—5]. 相似文献
5.
是一一映射。(参见[1、2]) 简单图G_1=(V_1,E_1)与G_2=(V_2,E_2)的积图G=G_1×G_2=(V,E)指的是:V=V_1×V_2,而点(v_1,v_2)与(ν′_1,v′_2)间有边且或且。 本文讨论积图P_m×C_(4n)的k-优美性,这里m,n,k皆为正整数,而P_m表示m个点的链,C_(4n)表示4n个点的简单回路。 相似文献
6.
一、一个猜想设 P_n 为具有 n 个顶点的一条路,它的 n-1条边着上了不同的颜色,若这个着色能扩充为 n 个顶点的完全图 K_n 的一个正常的 x′(K_n)一边着色,则称边着色路 P_n 能嵌入于完全图.一般说来,设 G 是具有边色数 x′(G)的一个简单图,令 M(G)为 G 中所有满足以下性质的子图 H(?)G 的集合:存在 G 的一种正常的 x′(G)-边着色使得 H 的各条边具有不同的颜色.设 K_n 是 n 个顶点的完全图,把集合 M(K_n)简记为 M_n 于是我们一开始提出的问题“P_n 能否嵌入于完全图”等价于“P_n 是否属于 M_n”. 相似文献
7.
8.
9.
10.
令H,G是两个简单图,G是H的一个子图.H的G-分解,记为(λH,G)-GD,是指将图λH的所有边分拆为若干个与G同构的子图(称为G-区组).H的G-分解的大集,记为(λH,G)-LGD,是指图H的所有与G同构的子图的一个分拆Β1,Β2,…,Βm,使得每个Bj(1≤j≤m)为一个(λH,G)-GD (称为小集).本文中,我们对完全二部图的K(p,p)-分解的大集进行了研究,利用Kv的λ重Kκ-因子大集的存在性结果,采用直接构造的方法,得到了大集(λK(m,n),K(p,p))-LGD的存在谱,其中p为任意素数. 相似文献
11.
设G=(V(G),E(G))是一个简单连通图,V(G),E(G)分别表示图G的顶点集和边集.如果与图G同Laplacian谱的图都与G同构,则称图G由它的Laplacian谱确定.该文定义了两类双圈图Q(n;n_1,n_2,···,nt)和B(n;n_1,n_2),证明了双圈图Q(n;n_1),Q(n;n_1,n_2),Q(n;n_1,n_2,n_3)和双圈图B(n;n_1,n_2)分别由它们的Laplacian谱确定. 相似文献
12.
本文只讨论单纯图。所有符号的意义均同于[2]。依照[1]给出定义 如图 G=(V,E)具有性质:λ(G)=k,而对(?)e∈E 均有λ(G-e)=k-1,则称 G 为极小 k 边连通图。设已给图 G=(V,E),如果 A,B(?)V,且 A∩B=φ,则记[A,B]={xy↓x∈A,y∈B,xy∈E}。如果 S(?)E,|S|=k,且 G-S=G_1 U G_2 V(G_1)∩V(G_2)=φ,V(G_1)≠φ, 相似文献
13.
14.
设G=(X,Y,E(G))是一个二分图,分别用V(G)=X∪Y和E(G)表示G的顶点集和边集.设f是定义在V(G)上的整数值函数且对任意x∈V(G)有f(x)≥k.设H1,H2,…,Hk是G的k个顶点不相交的子图,且|E(Hi)|=m,1≤i≤k.本文证明了每个二分(0,mf—m+1).图G有一个(0,f)-因子分解正交于Hi(i=1,2,…,k) 相似文献
15.
本文从两个图笛积的定义,定义了两个图的邻接矩阵的笛积,并讨论了这种新的矩阵乘积的性质.本文利用矩阵的笛积,证明了 A.K(?)tzig 在1963年所作的关于 n 个图笛积的 H-分解的猜测:如果图 G_1,G_2,…,G,都恰好可以分解成 s 个 H-圈,则 G_1×G_2×…×G(?)可以分解成 r·s 个 H-圈.本文将结果推广到任意图. 相似文献
16.
关于图中子图的(n,k)—正交因子分解 总被引:1,自引:0,他引:1
设G是一个具有顶点集V(G)和边集E(G)的图.
设g和f是定义在V(G)上的两个整数值函数,使得g(x)f(x)对所有的点x∈V(G)都成立.如果G是一个(mg+n,mf-n)-图,1n<m2k,且g(x)2k-1对所有的点x∈V(G)都成立,则对任意给定具有|E(H)|=nk边的G的子图H,存在G的一个子图G′使G′有一个(g,f)-因子分解(n,k)-正交H. 相似文献
17.
18.
19.
Ramsey数R(K_3,K_(16)-e)的一个下界 总被引:2,自引:0,他引:2
图论方法是研究Ramsey理论中最常用的方法,80多年的研究产生了大量的成果.Ramsey数R(G,H)是这样的最小正整数n,使得完全图K_n的边的任何一种红、蓝染色都会有一个红色边子图G,或者有一个蓝色边子图H.本文找到Ramsey数R(K_3,K_(16-e))的一个下界. 相似文献
20.
这里考虑的一切图均为简单的,以V(G),E(G)分别表示图G的节点集和边集。设H是G的子图,x∈V(H),用d_H(x)表示H中与节点x相邻节点的个数。如果e=(x,y)∈E(H),x,y是e的端点,则让d_H(e)=d_H(x)+d_H(y)。设A、B是V(G)的两个节点不交的子集,用E(A:B)表示G中一端在A中另一端在B中边的个数。设M是G 相似文献