非连通图(P1∨Pn)∪Gr和(P1∨Pn)∪(P3∨r)及Wn∪St(m)的优美性

讨论非连通图((P₁∨P_n)∪G_r和(P₁∨P_n)∪(P₃∨_r)及W_n∪St(m)的优美性, 证明了如下结论： 设n,m为任意正整数, s=［n/2］, r=s-1, G_r是任意具有r条边的优美图, 则当n≥4时, 非连通图((P₁∨P_n)∪G_r和(P₁∨P_n)∪(P₃∨_r)是优美图； 当n≥3, m≥s时, 非连通图W_n∪St(m)是优美图. 其中, P_n是n个顶点的路, K_n是n个顶点的完全图, n是K_n的补图, G₁∨G₂是图G₁与G₂的联图, W_n是n+1个顶点的轮图, St(m)是m+1个顶点的星形树.     

两类非连通图(P_2∨)∪St(m)及(P_2∨)∪T_n的优美性

对自然数n,m,i∈N,设Ki表示i个顶点的完全图,Kn是Kn的补图,St(m)表示m+1个顶点的星形树,Tn为n个节点的优美树,Pn为n个节点的路,P2∨Kn是P2与Kn联图.给出非连通图(P2∨Kn)∪St(m)和(P2∨Kn)∪Tn,并论证了当n≥2时,这两类图都是优美图.     

有关图(P(1)1∨Pn)∪(P(2)1∨P2n)和(P2∨n)∪Gn-1优美性研究

文章给出了非连通图(P1∨Pn)∪St(m)和(P(1)1∨Pn)∪(P(2)1∨P2n)及(P2∨n)∪Gn-1,证明了对任意自然数n,设s=(n)/(2),则当n≥3,m≥s时,非连通图(P1∨Pn)∪St(m)是优美图;当n≥3时,非连通图(P(1)1∨Pn)∪(P(2)1∨P2n)是s-优美图;当n≥2时,非连通图(P2∨n)∪Gn-1是优美图;其中,Pn是n个顶点的路,P1、P(1)1和P(2)1均是只有一个顶点的平凡图,G1∨G2是图G1与G2的联图,St(m)是m 1个顶点的星形树,Kn是n个顶点的完全图,n是Kn的补图,Gn-1是任意一个n-1条边的优美图.     

两类非连通图(P2∨(Kn))(0,0,r1,0,…,0,rn)∪St( m)及(P2∨(Kn))(r1+a,r2,0,…,0)∪Gr的优美性

对自然数n,m,i∈N,设Ki表示i个顶点的完全图,(Kn)表示Kn的补图,St(m)表示m+1个顶点的星形树,G,为有r条边的优美图,Pn为n个节点的路,P2 ∨(Kn)是P2与(Kn)联图.给出了非连通图(P2 ∨(Kn))(r1,r2,0,…,0)∪St(m)及(P2∨(Kn))(r1 +a,r2,0,…,0)∪Gr的定义,并论证了当n≥2时,这两类图都是优美图.     

两类非连通图（P2∨■）（0,0,r1,0,…,0,rn）∪St（m）及（P2∨■）（r1+a,r2,0,…,0）∪Gr的优美性

对自然数n,m,i∈N,设Ki表示i个顶点的完全图,■表示Kn的补图,St(m)表示m+1个顶点的星形树,Gr为有r条边的优美图,Pn为n个节点的路,P2∨■是P2与Kn联图。给出了非连通图(P2∨■)(r1,r2,0,…,0)∪St(m)及(P2∨■)(r1+a,r2,0,…,0)∪Gr的定义,并论证了当n≥2时,这两类图都是优美图。     

非连通图(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个顶点的圈.     

非连通并图的优美标号研究

设图G3是长度为3的圈C3或为含3个顶点的路P3,文章给出了非连通图(G3∨Km)∪Kn,t和(G3∨Km)∪Pn,并证明了对任意正整数m,n,t,如果min{n,t}≤m,则图(G3∨Km)∪Kn,t是优美图;如果2≤n≤2m+1,则图(G3∨Km)∪Pn是优美图;同时证明了对任意正整数m,n,图(G3∨Km)∪St(n)和(G3∨Km)∪W2n+5是优美图.其中,Pn是n个顶点的路,G1∨G2是图G1与G2的联图,Km是m个顶点的完全图,m是Km的补图,Kn,t是具有二分类(X,Y)的完全偶图,且|X|=n,|Y|=t,St(n)是具有n+1个顶点的星形树,Wn是具有n+1个顶点的轮图.     

非连通图（P2∨Kn）(r1,r2,…,rn+2)∪Gr的优美性

对自然数n∈N,设Kn表示n个顶点的完全图,Kn表示Kn的补图,Gr为有r条边的优美图,Pn为n个节点的路,P2∨Kn是P2与Kn的联图.给出了非连通图(P2∨Kn)(r1,r2,…,rn+2)∪Gr的定义,论证了当n≥1时,这类图是优美图.     

Gracefulness of disconnected graphs W(k)m∪G

文章证明了对任意自然数n≥1,P≥1,K≥1,当m1=2p+3或2p+4时,图W(k)m1U Kn,p为优美图,其中W(k)m1为由k个轮Wmi(i=1,2,…,k)的中心顶点合并后构成的连通图;当m1≥3,n≥[m1/2]时,非连通图W(k)m1∪St(n)为优美图;对任意自然数P≥1,图W(k)2p2+i∪Gpi为优美图,其中,Gpi表示p条边的i-优美图(i=1,2);对任意自然数n≥1,当m1=2n+5时,图W(k)m1∪(C3VKn)为优美图.     

非连通图(K_1∨(P_n~(1)∪P_n~(2)))∪P_n~(3)及(K_1∨(P_n~(1)∪P_n~(2)))∪St(n)的优美性

给出了非连通图(K1∨(P(1)n∪P(2)n))∪P(3)n和(K1∨(P(1)n∪P(2)n))∪St(n),且对其优美性进行了研究。证明了如下结论:设n为任意正整数,则当n≥4时,非连通图(K1∨(P(1)n∪P(2)n))∪P(3)n和(K1∨(P(1)n∪P(2)n))∪St(n)均是优美图;其中,Pn是n个顶点的路,Kn是n个顶点的完全图,St(n)是n+1个顶点的星形树,G1∨G2是图G1与G2的联图。     

基于最省刻度尺构造极小优美图的图论方法

[目的]利用最省刻度尺的已有研究成果研究极小优美图的构造方法.[方法]对任意正整数n≥2,在长度是n的无刻度直尺上最少刻多少个刻度,就能度量1-n的所有长度,这就是最省刻度的尺子问题.给定正整数n,存在m个整数组成的集合{a_i},满足0=a₁2<…m=n,使得任意整数s(0≤s≤n)均可表示成该集合中两个元素的差a_j-a_i,则称{a_i}为n上的受限差基.根据极小优美图和受限差基的定义,将极小优美图问题等效为最省刻度尺问题进而得到极小优美图的构造方法.[结果]由n≥5时K_n不是优美图和n≥1时图K₄+K_n,n是优美图的结论,得到了边数是6至82的极小优美图顶点数的上下界;用构造方法给出了图K₃∨K_1,3,n-3e,K_3,n∨K₃-e和K_2,3,n     

图C7 (r1,r2,r3, r4,r5,0,0)∪St(m)的优美性

圈C₇的(r₁,r₂,r₃,r₄,r₅,0,0)-冠简记为C₇(r₁,r₂,r₃,r₄,r₅,0,0),St(m)表示有m+1个顶点或有m条边的星型树.讨论了C₇(r₁,r₂,r₃,r₄,r₅,0,0)与St(m)的非连通并集C₇(r₁,r₂,r₃,r₄,r₅,0,0)∪St(m)优美性,用构造性的方法给出了一些特殊的C₇(r₁,r₂,r₃,r₄,r₅,0,0)∪St(m)的优美标号.     

2-连通P3-支配图的Hamilton圈

如果图G中任意一对距离为2的顶点x,y,有J(x,y)∪J′(x,y)≠Φ,则称G为P₃-支配图。本文证明了：设G是n(≥3)阶2-连通P₃-支配图,如果对G中任意一对不相邻的顶点x,y,有2|N(x)∪N(y)|+d(x)+d(y)≥2n-5,则G含有Hamilton圈或者G∈{K_2,3,K_1,1,3}。     

非连通图Wmk∪G的优美性

文章证明了对任意自然数n≥1,p≥1,k≥1,当m1=2p+3或2p+4时,图W(k)m1∪Kn,p为优美图,其中Wm1(k)为由k个轮Wmi(i=1,2,…,k)的中心顶点合并后构成的连通图;当m1≥3,n≥[m1/2]时,非连通图Wm1(k)∪St(n)为优美图;对任意自然数p≥1,图W2p+2+i(k)∪Gip为优美图,其中,Gpi表示p条边的i-优美图(i=1,2);对任意自然数n≥1,当m1=2n+5时,图Wm1(k)∪(C3∨■)为优美图。     

扇形图P1 ∨ Pm中保Wiener指数的树

Wiener指数是指一个连通图中所有顶点之间的距离之和.给定一个连通图G,若存在G中一棵子树T,使得W(G)=W(T),则称T为G的一可保Wiener指数的树.对于满足下列条件之一的m 1阶的扇形图P1∨Pm,证明了P1∨Pm中均有保Wiener指数的子树(i)m=t2 4t 1(t为任意正整数);(ii)m=21(t2 5t 3)(t≥6为正整数).     

具有特定分解集的图的Turán数

主要研究了具有特定分解集的图的Turán 数,通过确定图F 的极值图,从而确定ex (n,F) 的精确值.具体来说,确定了通过将P₂∪P₃ 的每条边都用一个3团代替(其中每个团的新顶点都是不同的)而得到的图F₁ 的极值图,证明ex (n,F₁) ;确定了通过将完全二部图K_2,3 中的每条边都用一个5 长圈代替(其中每个圈的新顶点都是不同的)而得到的图F₂的极值图,证明ex (n,F₂)     

图Kn-Cn-1的沙堆群

一个连通图的沙堆群,又称临界群或雅可比群,是一个有限的阿贝尔群,其阶数为图中生成树的数目.本文用代数方法确定了K_n-C_n-1的沙堆群的结构,K_n-C_n-1表示从完全图K_n中删掉圈C_n-1上的n-1条边所得到的图.     

两类非连通图(P2∨Kn)（0，0,r1,0,…,0,rn)∪St(m)及(P2∨Kn)（r1+a,r2,0,…,0)∪Gr的优美性

 对自然数n, m, i∈N,设K_i表示i个顶点的完全图,K_n表示K_n的补图,St(m) 表示m+1个顶点的星形树,G_r为有r条边的优美图,P_n为n个节点的路,P₂∨K_n是P₂与K_n联图。 给出了非连通图(P₂∨K_n)（0,0,r₁,0,…,0,r_n)∪St(m)和(P₂∨K_n)（r₁+a,r₂,0,…,0)∪G_r的定义,并论证了当n≥2时,这两类图都是优美图。     

n维无向超环面网的(l,2n)控制数

对于m连通图G,宽直径d_m(G)是指最小正整数d使得图G中任何两顶点x和y间都存在m条内点不交且每条长度不超过d的路.顶点集V(G)的子集S称作(l,m)控制集,如果顶点■x∈V(G)-S,都存在m条从S到x内点不交且每条长度不超过l的路.G的所有(l,m)控制集中顶点个数的最小值称为(l,m)控制数.若[f(d₁,d₂,…,d_n)」+3≤l≤d_G(C(d₁,d₂,…,d_n),可知无向超环面网C(d₁,d₂,…,d_n)的(l,2n)控制数为2,其中f(d₁,d₂,…,d_n)=1/2■e’i,n≥4,d_i≥5(i=1,2,…,n).     

关于图n∪i=1(～P)4和n∪i=1(～P)8的优美性

棱柱图(～P)n是由2个回路v1,v2,v3,…,vn和u1,u2,u3,…,un,加上边uivi后所组成的图形.图n∪i=1(～P)4是n个(～P)4的不交并图,图n∪i=1(～P)8是n个(～P)8的不交并图,证明了2类非连通图n∪i(～P)4和n∪i=1(～P)8是优美图且是交错图.