共查询到18条相似文献,搜索用时 187 毫秒
1.
用P(G,λ)表示简单图G的色多项式.设G是一个给定的简单图,若对任意简单图H,当P(H,λ)=P(G,λ)时都有H和G同构(记为H≌G),则称图G是色唯一的.本文证明了以下结果:设n,k,△都为非负整数,其中k≥0,△∈{4,5},若n≥1/3k~2+1/3△~2-1/3k△-1/3k-1/3△+4/3,则完全三部图K(n,n+△,n+k)是色唯一的.同时还给出了一个猜想. 相似文献
2.
设P(G,λ)是图的色多项式。如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.这里通过比较t 1色类的色划分数目,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,当min(n1,n2,…,nt)充分大时,完全t部图K(n1,n2,…,nt)是否是色唯一图?)。改进了文献[5]中的结果。证明了若Σ1≤i≤ta2i=T,min{n a1,n a2,…,nt at,n-1}≥(T 1)/2,则K(n a1,n a2,…,n at)是色唯一图(其中ai是实数,n ai是正整数)。从而证明了若|ni-nj|≤k(i,j=1,2,…,t),min{n1,n2,…,nt}≥tk2/8 1,则K(n1,n2,…,nt)是色唯一图。 相似文献
3.
Let P(G,λ) be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P(H,λ) = P(G,λ) implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 31m2 + 31k2 + 31mk+ 31m? 31k+ 32√m2 + k2 + mk, where n,k and m are non-negative integers, then the complete tripartite graph K(n - m,n,n + k) is chromatically unique (or simply χ-unique). In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 31m2 + 31k2 + 31mk + 31m - 31k + 43, then the complete tripartite graph K(n - m,n,n + k) is χ-unique, which is an improvement on Zou Hui-wen's result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture. 相似文献
4.
完全三部图K(n_1,n_2,n_3)的色唯一性 总被引:4,自引:0,他引:4
设G是简单图,用P(G,λ)表示图G的色多项式.若对任意简单图H使P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图.令K(n 相似文献
5.
关于完全t部图K(n1,n2,…,nt)的色唯一性 总被引:1,自引:1,他引:0
设P(G,λ)是图G的色多项式,如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称G是色唯一图。这里通过比较图的特征子图的个数,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,1≤i,j≤t且min{n1,n2,…,nt}充分大,K(n1,n2,…,nt)是否为色唯一图?)。证明了,若|ni—nj|≤2且t↑∑↑i=1 ni〉t^2/2+t√t-1,则K(n1,n2,…,nt)是色唯一图;若αi=0或k,t↑∑↑i=1 n+αi〉t^2k^2/8+|tk|/2√t-1,则K(n+α1,n+α2,…,n+αt)是色唯一图。其条件比文献[4]中的条件较好一些。 相似文献
6.
广义轮图的色多项式唯一性 总被引:4,自引:0,他引:4
本文证明了:当k≥0,n≥4为偶数时,广义轮图θn,k色多项式唯一。同时,也用较简单的方法证明了:对于一个图G,其色多项式为Pλ(G)=λ…(λ-q+1)·(λ-q)n-q当且仅当G为n阶q-树。 相似文献
7.
设P(G,λ)是图G关于变量λ的色多项式,P(G,λ)=P(H,λ),称G和H色等价,由连接两个顶点的S条内部不交的路组成的图叫S-桥图。本讨论了5-桥图F(2,a,a,b,c)(c≥b≥a 1,a≥2)的色性,完整刻画了这类图的色等价图。 相似文献
8.
9.
10.
设S是完全图Km 1的任一有s条边的子图,即|E(S)|=s,E(S)(∪)E(Km 1),V(S)(∪)V(Km 1).图Km 1-E(S)简单地表示为Km 1-S,而Km 1-S关于Km 1的补图记为(Km 1-S).空图Nm与(Km 1-S)的联图记为Nm∨(Km 1-S).K sm 1(m,m 1)表示图集{Nm∨(Km 1-S)| S是Km 1的子图,|S|=s}.本文证明了当m≥s 2且s≥1,〈S〉是E(s)在完全图Km 1的边导出子图并且〈S〉是二部图时,联图Nm∨(Km 1-S)为色唯一图的充要条件是〈S〉是没有割点的连通图(即〈S〉是2-连通的或〈S〉≌Ki,i=1,2)且是色唯一图. 相似文献
11.
设n,m和r是满足r≥2,n≥0,m≥3的整数,且当r是奇数时,假设r≥m-1.称一个图为K1,m-free,如果它不包含以Kt,m为导出的子图.称一个图G为一个(r,n)-临界图,如果在删去G的任意n个点后,剩下G的子图都有一个r-因子,设G是一个Kl,m-free的(n+1)-连通图,且阶为|G|以及r(|G|≥n)是偶数,证明了:如果G的最小度至少是r+n+m-1,阶|G|≥8r5+n,并且对V(G)的任意独立点集{x1,x2}都有|NG(x1)∪NG(x2)|≥(|G|+n)/2,那么G是一个(r,n)-临界图.关于G的最小度和|NG(x1)∪NG(X2)|的下界是紧的。 相似文献
12.
设G是一个简单图, f是定义在V(G)上的整数值函数,且m是大于等于2的整数. 讨论(0, mf-k+1)-图G的正交因子分解, 并且证明了对任意的1≤k≤m, (0, mf-k+1)-图G中存在着一个子图R, 使得R有一个(0,f)-因子分解正交于图G中的任意一个k-子图H. 相似文献
13.
λKn(t)是一个λ重完全多部图,G为一个不带孤立点的简单图.所谓的图设计G-HDλ(tn)是一个序偶(X,B),其中X是Kn(t)的顶点集,B为λKn(t)的一些子图(亦称为区组)构成的集合,使得任一区组均与图G同构,且λKn(t)的任意2个不同点组成的边恰在B的λ个区组中出现.本文讨论了G=K2,3的完全多部图设计存在性问题,证明了存在G-HDλ(tn)当且仅当λn(n-1)t2≡0(mod12),n≥2,nt≥5且(n,,λt)≠(9,1,1),(12,1,1),(3,1,2),(4,1,2). 相似文献
14.
郝萃菊 《数学的实践与认识》2014,(4)
设G是m阶连同图,我们用S_n~G(n=km+1)表示把kG的每个分支的d_i度点分别与星图S_k+1的k个1度点重迭后得到的图,Y~(SG)(r_1n,n)表示把r_1S_n~G中每个分支的k度点依次与图的k度点邻接后得到的图,Y~(SG)(r_2λ_1,n)表示把τ_2Y~(SG)(τ_1n,n)中每个分支的r_1+k度点依次与图S_n~G的k度点邻接后得到的图,若k≥3,用Y~(sG)(r_kλ__(k-1),n)表示把τ_kY~(sG)(r_(k-1)λ_(k-2),n)中每个分支的τ_(k-1)+k度顶点依次与图S_n~G的k度点邻接后得到的图,这里λ_k=r_kλ_(k-1)+n.运用图的伴随多项式的性质,证明了一类新的图簇Y~(sG)(r_kλ__(k-1),n)∪β_kS_n~G的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价图. 相似文献
15.
令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了Ν(G,Kt)≤(n-k)(k t-1)+(k t).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了Ν(G,Ks,t)≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s.此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数.记v(G),K(G)分别为图G的最大匹配数和最小点覆盖.证明了当v(G)≤k,K(G)=k+r且n≥2k+2r2+r+1时,有e(G)≤(k+r+1 2)+(k-r)(n-k-r-1). 相似文献
16.
设G是m阶连通图,Pm是m个顶点的路.令Skm+1G(i)表示把kG的每一个分支的第i(1≤i≤m)个顶点依次与星图Sk+1的k个1度顶点重迭后得到的图;令Gi1S*(q,km)表示q阶图G的顶点Vi1与Skm+1p(1)的k度顶点重迭后得到的图 相似文献
17.
Let K(p, q), p ≤ q, denote the complete bipartite graph in which the two partite sets consist of p and q vertices, respectively. In this paper, we prove that (1) the graph K(p, q) is chromatically unique if p ≥ 2; and (2) the graph K(p, q) - e obtained by deleting an edge e from K(p, q) is chromatically unique if p ≥ 3. The first result was conjectured by Salzberg, López, and Giudici, who also proved the second result under the condition that q - p ≤ 1. 相似文献
18.
Let P(G, λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H, λ) = P(G, λ) implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.: A complete solution to a conjecture on chromatic uniqueness of complete
tripartite graphs. Discrete Math., 289, 175–179 (2004)], and Lau and Peng [Lau, G. C., Peng, Y. H.: Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353–376 (2009)] show that K(p − k, p − i, p) for i = 0, 1 are chromatically unique if p ≥ k + 2 ≥ 4. In this paper, we show that if 2 ≤ i ≤ 4, the complete tripartite graph K(p − k, p − i, p) is chromatically unique for integers k ≥ i and p ≥ k
2/4 + i + 1. 相似文献