路与圈的优化t-pebbling数（英文）

图上的一个pebbling移动,是从图的一个顶点同时移除2个pebbles,并且在其某个邻点上放置1个pebble.图的优化t-pebbling数,记为f′t(G),是指图G中所需要的pebbled的最小数目,使得存在该f′t(G)个pebbles在图上的一种分布,可以在经过一系列pebbling移动后,t个pebbles可以移动到任意一个给定的目标顶点上.f′(G)=f′1(G)称为图G的优化pebbling数.这里给出了路Pn和圈C5的优化t-pebbling数,证明了f′9t(P2×P3)=20t;f′9t+1(P2×P3)=20t+3;当2≤r≤8时,20t+2r+1≤f′9t+r(P2×P3)≤20t+2r+2,其中,当5≤r≤8时,最后一个不等式取到等号.     

非连通图C_8(r_1,0,r_2,0,…,0)∪G的交错标号

讨论非连通图C8(r1,0,r2,0,…,0)∪G的优美性,证明当r1,r2为任意自然数、G是特征为k且缺k+3标号值的交错图(3≤k+3|E(G)|)时,非连通图C8(r1,0,r2,0,…,0)∪G存在缺标号值k+1的特征为k+5的交错标号,其中C8是具有8个顶点的圈,C8(r1,0,r2,0,…,0)是圈C8的(r1,0,r2,0,…,0)-冠.     

再探非连通图C4m-1∪C12m-8∪G的优美标号

讨论了非连通图C4m-1∪C12m-8∪G的优美性,证明了当m为任意正整数,G是特征为k且缺标号值k+6m-4的交错图(6m-4≤k+6m-4≤|E(G)|)时,非连通图C4m-1∪C12m-8∪G存在缺标号值k+16m-9的优美标号,其中,Cm是具有m个顶点的圈.     

关于支配圈和支配路的存在性

圈C称为图G的支配圈,若对G中任一点v,至少有圈C上的一个顶点与之邻接.类似定义图G的支配路.本文讨论了图中支配圈和支配路的存在性,得到下列结果:(1)设G是有n个顶点,ε条边的k-连通图(k≥1),若ε>((n-k)/2)~2-(3n-k)/2+4,则G中存在支配圈.(2)设G是有n个顶点的k-连通图(k≥2),若对图G中任何有k个顶点的独立点集{v_0,v_1,…v_(k-1)},满足N(v_i)∩N(v~i)=φ(0≤i≠i≤k-1),有~(k-1)∑_(i=0)d(v_i)>n-2(k+2)成立,则G中存在支配路.     

(4)-泛圈图的一个必要条件

(k)-泛圈图是指对每一个r(3≤r≤n),阶为n的图G恰好有k个长为r的圈.本文主要探讨只含有2对缠绕弦的(4)-泛圈图中包含2对缠绕弦的生成子图结构以及其阶.     

Cn与1Cn的优美标号

设k1,k2,…,kn是非负整数,Cn=v1v2…vnv1是有n个顶点n条边的圈,则称图Cn+{v1v11,v1v12,…,v1v1k1,v2v21,…v2v2k2,…,vnvn1,…,vnvnkn}为(k1,k2,…,kn)轮环图,简记为C(k1,k2,…,kn)·本文研究了圈Cn与图C(k1,k2,…,kn)的优美性,给出图Cn与1Cn在n=4k与n=4k+3时的优美标号算法,从而证明了它们都是优美图等结论.     

B.D.Acharya和S.M.Hegde关于算术图一个猜想的证明

B．D．Acharya和S．M．Hcgdc猜想[1]：(1)、如果圈C4t 1是(k,d)的算术图，那么必有k=2td 2r，其中r是某个非负整数；(2)如果圈C4t 3是(k，d)算术图，则k=(2t 1)d 2r，其中r是某个非负整数。本文对以上猜想给出了肯定性证明。     

折叠超立方体网络的t/k诊断问题

为提高系统故障诊断的诊断度,Somani 和Peleg提出了t/k诊断故障策略. n维折叠超立方体网络是具有2n个顶点,(n+1)2n-1条边的(n+1)-维正则图,它是n维超立方体网络增加2n-1补边得到的.中证明了当n≥6和1≤k≤n+1时n维超立方体网络是t/k可诊断的,其中t=(k+1)(n+1)-1/2(k+1)(k+2)+1.     

非连通图(C_(n_1)⊙r_1K_1)∪(C_(n_2)⊙r_2K_1)∪P_2的优美性

讨论非连通图(Cn1⊙r1K1)∪(Cn2⊙r2K1)∪P2的优美性,证明如下结论:设n1,n2,r1,r2是任意自然数,n1≥1,n2≥1,当n1(r1+1)=n2(r2+1)或3n1(r1+1)=n2(r2+1)时,(C4n1⊙r1K1)∪(C4n2⊙r2K1)∪P2是交错图;当n1(r1+1)=n2(r2+1)或(3n1-1)(r1+1)=n2(r2+1)时,非连通图(C4n1-1⊙r1K1)∪(C4n2⊙r2K1)∪P2是优美的,其中P2是2个顶点的路,Cn是n个顶点的圈,Cm⊙rK1是圈Cm的r-冠.     

图中具有指定性质的独立4-圈

主要给出了图G恰好含有s个K3和k-s个K4的最小度条件即:设G是一个简单图,s,k是两个正整数且s k,其中G的顶点个数n≥3s+4(k-s)+3,如果G中任意两个不相邻顶点的最小度之和σ2(G)≥4n-3s-8/|2|或者最小度δ(G)≥3n+2k-s-2/4,则G包含k个顶点不相交的圈C1,C2…Ck,并且Ci=K3其中1≤i≤s,Cj=K4其中sj≤k.     

非连通图（P3∨■）∪G及（C3∨■）∪G的优美性

将k-优美图的概念进行了推广,引入A～B优美图的概念,并以此为基础,得到了非连通图(P3∨■)∪G及(C3∨■)∪G是优美图的一个充分条件。证明了对任意正整数k,m,n,t,当k≤n≤t,n+k-1≤m时,图(P3∨■)∪(∪kj=1Kn,t)和(C3∨■)∪(∪kj=1Kn,t)是优美图;当k=1,2,2≤n<2m+1时,图(P3∨■)∪∪kj=1P(j)n,(C3∨■)∪∪kj=1P(j)n和(P3∨■)∪Pn∪St(t)是优美图;当2≤n≤2m+1时,(C3∨■)∪Pn∪St(t)是优美图。本文的结果推广了现有的一些结论。     

非连通图(P_1∨P_m)∪C_(4n)∪P_2的优美性

讨论非连通图(P1∨Pm)∪C4n∪P2的优美性.证明如下结论:设m、n为任意正整数,当m≥2,1≤n≤2m-2时,非连通图(P1∨Pm)∪C4n∪P2是优美图,其中Pn是n个顶点的路,G1∨G2是图G1与G2的联图,C4n是4n个顶点的圈.     

非连通图(P3∨(Km))∪G及(C3∨(Km))∪G的优美性

将k-优美图的概念进行了推广,引入A～B优美图的概念,并以此为基础,得到了非连通图(P3∨(Km))∪G及(C3∨(Km))∪G是优美图的一个充分条件.证明了对任意正整数k,m,n,t,当k≤n≤t,n+k-1≤m时,图(P3∨(Km))∪(k∪j=1Kn,t)和(C3∨(Km))∪(k∪j=1Kn,t)是优美图;当k=1,2,2≤n＜2m+1时,图(P3∨(Km))∪k∪j=1P(j)n,(C3∨(Km))∪k∪j=1P(j)n和(P3∨(Km))∪Pn∪St(t)是优美图;当2≤n≤2m +1时,(C3∨(Km))∪Pn∪St(t)是优美图.本文的结果推广了现有的一些结论.     

关于方程sum from j=0 to (n-1)(x+jr)~t=(x+nr)~t

V.A.Lebesque1 曾经证明方程 在t=3时,仅有正整数解n=3,x=3r。本文证明了方程(1)在4≤t≤10时无正整数解。由于(1)对于x和r是齐式的,所以我们可以假定(x,r)=1。对于方程(1),有下面的一些性质。引理1.n≥2t+2,k≤t,则有     

圈C_4的(S(tr+1),S(tr+2),S(tr+1),S(tr+2))-冠的优美性

本文给出了圈C4的(S(t r+1),S(t r+2),S(t r+1),S(t r+2))-冠的定义,讨论了圈C4的(S(t r+1),S(t r+2),S(t r+1),S(t r+2))-冠的优美性,用构造性的方法给出了圈C4的(S(t r+1),S(t r+2),S(t r+1),S(t r+2))-冠的优美标号.     

两类图族的Merrifield-Simmons指标的最大值

图族Q(Ck;Cs1,Cs2,…,Csk),Q(Pk;Cs1,Cs2,…,Csk),Q(Wk;Cs1,Cs2,…,Csk)分别是由圈C k,路P k和轮W k的每个顶点v i(i=1,2,…,k)(轮的中心顶点除外)分别顶点粘接圈C si(i=1,2,…,k)而得到的图;通过对图族Q(Ck;Cs1,Cs2,…,Csk),Q(W k;Cs1,Cs2,…,Csk)的Merrifield-Simmons指标进行研究,刻画出了这两类图族的Merrifield-Simmons指标(在顶点数一定时)取得最大值的图分别是Q(Ck;C4,C4,…,C4,C s1+s2+…+sk-4(k-1))和Q(Wk;C4,C4,…,C4,Cs1+s2+…+sk-4(k-1))。     

图Fm（t）的k-强优美性

文章通过对图Fm(t)的k-强优美性研究,利用k-强优美图的定义,给出对任意自然数t≥1,m≥2,当k=[m/2]时,Fm(t)是k-强优美图,非连通图Fm(t)∪Gk-1是优美图。当m≥2p+2时,非连通图Fm(t)∪Kn,p是优美图,其中,Fm是有m+1个顶点的扇形图,Fm(t)是合并t个扇Fm,F2 m,…,F2t-1m的中心顶点构成的连通图,Gk-1是有k-1条边的优美图。     

k-阶圈链Q(Cs1,P2,Cs2,…,P2,Csk)Hosoya指标最大值

图族k-阶圈链Q(C s 1 ,P 2,C s 2 ,…,P 2,C s k )是n个顶点的图,由k个圈C s 1 ,C s 2 ,…,C s k 通过使相邻两个圈C i和C i+1 (i=1,2,…,k 1)分别被路P 2的两个顶点点粘接而得到．通过对图族k-阶圈链Q(C s 1 ,P 2,C s 2 ,…,P 2,C s k )的 Hosoya 指标进行研究,刻画出该类图族的 Hosoya 指标取得最大值的图是Q(C 4,P 2,C 4,…,P 2,C n 4(k 1) )．     

图Cmk(P2,…,P2,Pl)的最大特征值

设圈C=v1 v2…vm v1,m≥3.在圈C的顶点vil,vi2,…,vik上分别悬挂k条路pn1,pn2,…,Pnk的图记为Ci1,i2….ik(Pn1,Pn2,…Pnk),其中1≤ij≤m,m,1 ≤j≤k.在顶点口vm上悬挂k条路Pn1,Pn2,…,pnk的图简记为Cmk(Pn1,Pn2,…,Pnk).利用图Cmk(P2,…,P2,P1)的特征多项式获得:λ1(Cmk+1(P2,…,P2,Pl-1))≥λ1(Cnk(P2,…,P2,Pl))≥2,其中,k,l ∈ N,l≥3.     

非连通图C4m-1∪C12m-8∪G的优美标号

讨论了非连通图C4m-1∪C12m-8 ∪G的优美性,证明了当m为任意正整数,G是特征为k且缺k＋6m-3标号值的交错图（6m-3≤k＋6m-3≤｜ E（G）｜）时,非连通图C4m-1∪ C12m-8∪G存在缺标号值k＋1的优美标号,其中,G是具有m个顶点的圈.