一个重构定理的推广

本文提出如下猜想:“给出P阶图G的P个主子图G_(19)G_2,…,G_(n-1),G_n,…,G_p,其中G_1,G_2,…,G_(n-1)中的V_1,V_2,…,V_n未标出,V_(n 1),V_(n 2),…,V_p标定,G_n,…,G_p中的点全不标号,则G可由G_1,G_2,…,G_(n-1),G_n…,G_p唯一地重构。”并且证明了:当n=3,4时,猜想为真。     

关于主子图中有若干部分标号图的重构猜想

文献[1]提出如下猜想:“给出p阶图G的p个主子图G_1,G_2,…,G_p,若对某个n,2≤n≤p,其中G_1…,G_(n-1)中点V_(n 1),V_(n 2),…,v_1已标正,V_1,…,V_n未标定;G_n,…,G_p中的点全不标号,则G可由这组G_1,…,G_(n-1),G_n,…,G_p(在同构意义下)唯一地重构。“当n=p时,这就是著名的Ulam重构猜想。”对2≤n相似文献   

关于部分标号图的重构

本文讨论部分标号图等邻集之间的邻接情况,证明了有n个点v_1,v_2,…,v_n未标出的р阶图G,当n=5或6时,可由主子图G_(i1),G_(i2),…,G_(in)(i_1,i_2,…,i_(n-1)相似文献   

关于六点未标的P阶图的重构问题

本文应用等邻集概念及补点法证明:“若给出P阶图G的6个主子图G_i(i=1,2,…,6),其中v_7,v_8,…,v_p已标号,其他的v_i未标号,则G可由G_i(i=1,2,… ,6)重构”.这一结果比文献[1]的结果更好.     

极大对集与最优投递路线问题(续)

§4. 问题2的解法(二)--最优判别定理定理4. 1(Edmonds,见[7] )。设 M 为 G 的一个对集,则 M 为长度极大对集的充要条件是:存在一个序列 G_0,G_1,…,G_s,满足:每一个 G_i 是一个图,G_i 的边 l_j 有长度 L_i(l_j),G_i 的点 V,有位势 W_i(V_k),G_i 中有一个对集 M_i。且下述条件都成立:(a)G_0=G;M_0=M;L_0(l_j)=L(l_j),j=1,…,m。(b)W_i(V_k)≥0,i=0,1,…,s,V_k 为 G_i 中任意一个点W_j(V_(j1) )+W_i(V_(j2) )≥L_i(l_j),i=0,1,…s,l_j 为 G_i 中任一边,V_(j1) ~-,V_(j2) 为 l_j 的     

同阶双轨道连通图的超圈边连通性

对于图G,如果G-F是不连通的且至少有两个分支含有圈,则称F为图G的圈边割.如果图G有圈边割,则称其为圈可分的.最小圈边割的基数叫作圈边连通度.如果去除任何一个最小圈边割,总存在一分支为最小圈,则图G为超圈边连通的.设G=(G_1,G_2,(V_1,V_2))为双轨道图,最小度δ(G)≥4,围长g(G)≥6且|V_1|=|V_2|.假设G_i是k_i-正则的,k_1≤k_2且G_1包含一个长度为g的圈,则G是超圈边连通的.     

部分标号图的重构问题

本文引入了“同邻点对”概念,应用此概念证明了定理1—4,连同作者以前的工作一起彻底解决了:“至多五点未标的P阶图G可由它的任意五个主子图重构”。这一结果比F.Haray和B.Manvel的结果前进了一大步。     

利用图的圈秩数进行边色数的分类

本文利用最大次顶点的导出子图的圈秩数研究了边色数的分类,得到下面的结果:定理1 设 G 为简单连通图,G_Δ为连通图,G_Δ的圈秩为 l,Δ(G_Δ)≤3,δ(G_Δ)≤2,Δ(G)≥1/2(|V (G)|+3l+1)+2l-1.则 G∈C~2G 含有满子图H,Δ(H)=Δ(G).     

关于链路P_n(m_1,m_2,…,m_(n-2))的k-优美性

图G的标号是指G的顶点集到一个整数集的映射g,且对e=uv∈E(G)由g(u)和g(v)诱导出边e的标号.本文给出了链路P_n(m_1,m_2,…,m_(n-2))的k-优美标号.即证明了图P_n(m_1,m_2,…,m_(n-2))是k-优美图.进而推广了原有的一些结果.     

一类OF型图及有关性质

讨论了OF-(-2)型图和OF-(-3)型图的有关性质,得到下列结果:(1)2n阶OF-(-3)型图中含有子图(n—1)K_2;(2)若2n阶OF-(-2)型图G中不存在1—因子,则G具有性质i)V_δ是有n+1个顶点的独立点集,ii)任给w,z∈V_δ,G—{w,z}中存在(n—1)个边不交1—因子,其中V_δ={v∈V(G)|d(v)=δ(G)}.结果(1)部分地改进了J.A.Bondy等人的一个结果。     

关于n-格图及相关图的L(2,1)标号问题

图G的L(2，1)标号是一个从顶点集V(G)到非负整数集的函数?（x），使得若d(x，y)=1，则|?（x）-?(y)|≥2；若d(x，y)=2，则|?（x）-?(y)|≥1。移动通讯频率分配问题可转化为图的L(2，1)标号问题。将2-格图及相关图推广到n-格图及相关图，并给出了它们的L(2，1)标号。     

几种正规积图的带宽

引言设G是个图,V(G)是G的顶点集,E(G)是G的边集。|V(G)|=n,如所周知,任一个1—1对应的函数f:V(G)→{1,…,n}均称为V(G)(或G)上的一个标号。规定f的带宽为B(f)=max{|f(u)-f(V)|:uv∈E(G)},而图G的带宽的定义则是B(G):min{B(f):f是G上的标号}。例如,图1即给出了一个很简单的图G_0的两种不同的标号:     

几类和扇有关图的优美性

证明下面的结论:对任意自然数n≥2,图(K_1∨(P_n∪P_(n+1)))是(n-1)-强优美图.对任意自然数n≥3,图(K_1∨P_n~((1))∪P_n~((2))))∪G是优美图;对任意自然数n≥4,图(K _1∨(P_n~((1))∪P_n~((2))∪P_n~((3)))∪H是优美图,其中k=[n/2].P_n是n个顶点的路,G_i为含有i条边的优美图.给定优美图G_(n-1)和其优美标号f,G_(k-1)和其优美标号g,设u∈G_(n-1),v∈G_(k-1)且f(u)=g(v)=0,取不同的两边xy和x′y′,点x与u合并后得到的图记为G,点x′与v合并后得到的图记为H.     

K-连通无爪图的最长u-路

本文证明了如下结果:设G是p阶K一连通的无爪图,K>2.G中任意K+1个顶点的独立集{V_1,V_2,…V_(k+1),有又设u∈V(G),为G中最长的u一路,则G[R]中不含(K-2)一路连通子图,从而不含K_(k-1),这里R=V(G)\V(P)。     

G映象的不动点指数和G_(γ~-)紧映象的不动点定理

本文引入了集值PF-映象,G映象,G_(γ~-)紧映象和集值映象的半可微概念,建立了G映象的不动点指数理论并获得了G_(γ~-)紧映象和具有半导数的G_(?)紧映象的许多非零不动点定理.     

关于图的L（d1，d2，d3）-标号问题

图G的L(2,1)-标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)-标号数λ(G)是使得G有max{f(v):v∈V(G)}=k的L(2,1)-标号中的最小数k.本文将L(2,1)-标号问题推广到更一般的情形即L(d1,d2,d3)一标号问题.并得出了一般图和平面图的λd1,d2,d3(G)的上界.     

一类新图的奇优美性的研究

设L为简单无向图G的一个顶点标号,L称为图G的奇优美标号,若L满足以下两条:(1)L为G的顶点集V到{0,1,…,2 ︱E︱-1}的一个单射;(2)由L′(e)=︳L(u)-L(v)︳(其中e=uv)决定的边标号L′是从G的边集E到{1,3,…,2 ︱E︱-1}的一个双射.本文给出了一类特殊简单图G*的奇优美标号,并给出了相应的标号算法及相关的一些证明.     

边替换图的邻和可区别全染色

考虑图的邻和可区别全染色问题及其相关的1-2猜想.首先,利用独立消圈集法得到剖分图S(G)和三角扩展图R(G)的邻和可区别全色数;其次,当G为任意简单连通图且T为给定的特殊图时,证明边替换图G[T]满足1-2猜想.     

关于图的L(3,2,1)-标号问题

图G的L(2，1)-标号是一个从顶点集V(G)到非负整数集的函数f(x)，使得若d(x，y)=1，则|f(x)-f(y)|≥2；若d(x，y)=2，则|f(x)-f(y)≥1．图G的L(2，1)-标号数A(G)是使得G有max{f(v)：v∈V(G)|=k的L(2，1)-标号中的最小数k．将L(2，1)-标号问题推广到更一般的情形即L(3，2，1)-标号问题，并得出了全图、块图的L(3，2，1)-标号数的上界．     

群的阶方程

本文引入有限群的阶方程的概念,讨论了阶方程的一些性质,证明了下面的结果:若G_1与G_2是n阶可换群,则G_1≌G_2(?)G_1与G_2有相同的阶方程。 定理1.设群G含有r个d阶元素,K_d个d阶循环子群,则r=k_dφ(d)。 证 由于d阶循环子群恰有φ(d)个生成元,而不同的d阶循环子群有不同的生成元,因此G的d阶元素的个数为k_dφ(d)。证毕。 定理2.设G是n阶群,则有n=>k_dφ(d),其中k_d为G的d阶循环子群的个数、k_dφ(d)是G的d阶元素的个数,并且有:1)k_1=1;2)若p是质数,且p|n,则k_p>0;3)若k_d>0,又d'|d,则k_d'>0;4)若G可换,且k_(d_1)>0,k_(d_s)>0,d_3=[d_1,d_2],则k_(d_3)>0。