共查询到17条相似文献,搜索用时 62 毫秒
1.
用P(t,d)(或者C(t,d))表示从一条长为d的简单路(或者简单圈)通过添加t条边后得到图的最小直径.证明了:如果t和d满足条件t≥4且t+4≤d≤t+7,或者t=4且d=10k+1(k≥1),那么P(t,d)=[d-2D+1]+1.对某些t和d,确定了C(t,d)的值和最好下界,部分地解决了Schoone等的猜想[J.GraphTheory,1987,11:409-427]. 相似文献
2.
证明了:对任何整数t≥6和d≥2,从一条长为d的简单路通过添加t条边后得到的图的最小直径上界为[d-2/t 1] 2,如果d∈J'(t,k)={2k(t 1) 1,2k(t 1) 2,2k(t 1)-t 1}∪{2k(t 1)-t h:h=6,7,…,t};其他情形为[d-2/t 1] 1.这个证明改进了已知结果,而且[d-2/t 1] 1是最好的上界. 相似文献
3.
给定任意正整数t和d(≥2),记P(t,d)为在直径d的路上加上t条边后所得图的最小直径.证明了:P(6,4)=1; 当d=5,6,7时有P(6,d)=2;当d=7(2k-1)+h(k≥1, 1≤h≤14) 时有(d)/(7)≤P(6,d)≤ (d)/(7)+2若h=7;(d)/(7)+1其他;当d=5,6,7,8时有P(7,d)=2;当d=8(2k-1)+h (k≥1,1≤h≤16)时有(d)/(8)≤P(7,d)≤ (d)/(8)若h=1;(d)/(8)+2若h=2,3,4,5,6,7,8;(d)/(8)+1其他. 相似文献
4.
赵承业 《牡丹江师范学院学报(自然科学版)》2006,(3):3-5
对于n个节点的无向路pn,令p(n,t)为pn中添加t条边后得到的变更图的最小直径.本文通过构造出一类变更图,改进了p(n,t)的上界. 相似文献
5.
彭锦 《华中师范大学学报(自然科学版)》1999,33(4):480-486
边愉快图是新近提出的研究课题,本文给出了边愉快图的必要条件和一类添加图或删边图成为边愉快图的充分条件;考察了几种常见图类的边愉快特征;构造了一类奇阶偶正则的边愉快图,给出了相应的边愉快标号方法;提出了值得进一步研究的一些问题。 相似文献
6.
7.
本文在文[1]的基础上,讨论了图的边优美问题,从而得到了一些特殊图边优美的必要条件和充分条件。 相似文献
8.
图G的一条边e称为G的同构不动边,如果G—e+e’≌G当且仅当e’=e.若e=uv是G的同构不动边,那么对G—e的任意自同构映射π有π({u,v})={u,v}.图的同构不动边反映了二元关系系统中的定性关系,改变这种关系将改变系统的结构.这种关系的存在对系统的重构有重要的意义.本文中猜想:几乎所有的图含同构不动边.为支持这个猜想,列出了所有不含同构不动边的树形图和单圈图. 相似文献
9.
设γ’st(G)表示图G的符号边全控制数,给出了一般图G和超立方体的符号边全控制数的一个下界和一个上界,计算了等完全二部图的符号边全控制数的精确值。 相似文献
10.
图G的非正常边着色,即(m·d)一边着色是把边集E(G)划分成m个子集E1,E2,…,Em,使得每一边子集的导出子图G〔Ei〕,i=1,2,…,m的最大度最多是d。Woodal问:对奇数d和自然数m,最大度是md的第二类图中哪些是(md)一边可着色的?哪些不是?本文对Woodal的这一公开问题给出了一些明确的解答。 相似文献
11.
12.
给出了k-连通图中最长圈上的可收缩边的数目,得到如下结果:任意断片的阶至少为「k/2+1 的k-连通图中最长圈上至少有3 条可收缩边;更进一步,若该k-连通图中存在哈密顿圈,则哈密顿圈上至少有6 条可收缩边。 相似文献
13.
用F(U3,n-2,1)表示围长为3、顶点数为n的单圈添加1条边后其变更图的最小直径.本文证明了当n为偶数时,其最小直径为n/2-1;当n为奇数时,其最小直径为「n/2」.该结论改进了已有结果,为进一步研究奠定了基础. 相似文献
14.
王倩 《山东大学学报(理学版)》2016,51(8):29-34
给出了k-连通图生成树和完美匹配上的可收缩边数目,得到如下结果:任意断片的阶都大于「k/2的k-连通图中生成树上至少有4条可收缩边;若该k-连通图中存在完美匹配,则完美匹配上至少有「k/2+1条可收缩边。 相似文献
15.
研究了树、圈、完全二部图和轮图的2-强边染色问题.对于树,给出了2-强边色数等于最大顶点度加1的充分条件;对于圈、完全二部图及轮图,求出了2-强边色数,并给出了相应的染色方案. 相似文献
16.
若干积图的点可区别边染色 总被引:2,自引:0,他引:2
证明了:(1)两个n(n2)阶完全图的积图的点可区别边色数为2n. (2)对阶至少是3的完全图Kn,若χ′vd(G)=Δ(G),则χ′vd(G×Kn)=n+Δ(G).(3)若χ′vd(Gi)=Δ(Gi),i=1,2,则χ′vd(G1×G2)=Δ(G1)+Δ(G2). 相似文献