阀门布局问题的一个最优性判别条件

给定非空点集x及其n对非空子集x_i,y_i,x_i∩y_i=φ(i=1,2,…,n)。找出一个图G,满足条件(a)V(G)=x;(b)对i=1,2,…,n,G皆有连通子图G_i,使x_i(?)V(G_i)和y_i∩V(G_i)=φ,且使|E(G)|最小。本文指出上述问题的一个最优性判别条件;并利用Hall定理及若干引理给出严格的数学证明。     

完全图上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v_(0i)|i=1,2,…,p}的简单图,n是正整数,称M_n(G)为G上的锥(或广义Mycielski图),如果V(M_n(G)={v_(01),v_(02),…,v_(0p);v_(11),v_(12),…,v_(1p);…v_(n1),v_(n2),…,v_(np),w}) E(M_n(G))=E(G)∪{v_(ij)v_((i 1)k)|v_(0j)v_(0k)∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{v_(nj)w|1≤j≤p}.在这篇文章里,我们讨论了完全图上的锥的$D(2)$-点可区别的正常边染色,并给出了相应色数.     

图可重构性的一点注记

设图G的顶点集为{v_1,v_2,…,v_n}.G的途径矩阵D(G)=(d_(ij)是n阶方阵,此处d_(ij)是G中从v_i出发长为j的途径数,D(G)的行向量集X的子集{x_1,x_2,…,x_r}称为X的最小线性相关集,如果{x_1,x_2,…x_r}线性相关且对X的任一(r-1)之子集均是线性无关.称数r为G的最小线性相关数.当X线性无关时,定义G的最小线性相关数r=∞.对1≤i≤n,记d_i为点v_i在G中的次,G_i是图G剔除点v_i以及与v_i关联的边而得到子图.设r_i是G_i的最小线性相关数,我们有下列定理:如果存在某一数i使r_i>2d_i,则G是可重构的.特别,我们重新得到下述结果:如果存在某一子图G_i,使得G_i的所有特征向量均不与C=(1,…,1)_t正交,则G是可重构的.     

关于Borel的一个定理

Borel的一个经典性定理是,如果两组整函数G_i(Z)(i=1,2,…,n)和H_i(Z)(i=1,2,…n)满足恒等式sum from j=1 to n G_i(Z)e~Hj~(Z)≡0 并且如果G_i(1≤i≤n)的增长性,在某种意义下,较慢于e~Hj~(-H)k(1≤j,k≤n,j≠k)的增长性,则G_i(Z)≡0 (i=1,2,…,n),在本文中得出了这个定理的几个推广。     

隔离性定理另证

这篇短文给出了下述定理的一个简明证明.定理 设F_1,F_2,…,F_n是数直线上的互不相交的非空闭集,则存在开集G_i(i=1,2,…,n)使得 G_i(?)F_i(i=1,2,…,n)且(?)_i∩(?)_j=φ(i≠j)     

半CAP-子群与有限群的p-超可解性

设G为有限群,H为G的子群.称H为G的半CAP-子群,如果存在G的一个主群列1=G_0 G_1…G_n=G,使得对每一个i=1,2,…,n,H或者覆盖G_i/G_(i-1),或者远离G_i/G_(i-1).该文主要利用Sylowp-子群的极大及极小子群的半覆盖-远离性来刻画有限群的结构,得到群为p-超可解或者p-幂零的几个充分或必要条件.     

关于G∪i=1^k Kmini的优美性

为加强对非连通图的优美性的研究，对于自然数k,mi,ni，给出一类非连通图G∪i=1^k Kmini通过构造标号函数的方法，证明了当max{mi,ni}≥3，min(mi,ni)≥2(i=1,2,…,k)时，这类图既是优美图，也是交错图，并进行了推广，得出由满足一定条件的交错图G和Gi(i=1,2,…，k)并起来的非连通图G∪i=1^n Gi是优美图，从而给出构造一类任意个交错图的并图是优美图的一种方法。     

图C_m·K_n的邻强边染色

将顶点集和边集分别为V={v_(ij)┃i=1,2,…,m;j=0,1,…,n-1},E={v_(10)v_(20),v_(20)v(30),…,v_(m0)v_(10)}U(Uim-1)(ij)ik┃j≠k,j,k=0,1,…,n-1}的图简记为Cm·Kn.利用图分解和色集置换的方法,给出了图Cm·Kn的邻强边色数。     

关于G(∪ki=1)Kmini的优美性

为加强对非连通图的优美性的研究,对于自然数k,mi,ni,给出一类非连通图∪k i=1Kmi,ni,通过构造标号函数的方法,证明了当max{mi,ni}≥3, min{mi,ni}≥2(i=1,2,…,k)时,这类图既是优美图,也是交错图; 并进行了推广,得出由满足一定条件的交错图G和Gi(i=1,2,…,k)并起来的非连通图G ∪ni=1G-i是优美图,从而给出构造一类任意个交错图的并图是优美图的一种方法.     

关于部分标号图的重构

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

若干n重积图的点可区别边色数

通过研究若干n重积图的边色数及点可区别边色数,就可证明■(Gi)=△(Gi),i=1,2,L,n,则∑=′×××=■△(G_i)其中G1×G2×L×Gn为G1,G2,L,Gn的n重积图.     

图F_m ▽S_n的边色数和邻强边色数

对图G的一个正常的k边染色法f,若 e∈E(G),e = uv,{f(uw) | uw∈E(G)}≠{f(vw) | vw∈E(G)},则称f为G 的一个k 邻强边染色法,k的最小值称为G 的邻强边色数.V(Fm Sn) = {w}∪{ui | i =1,2,…,m}∪{vij | i =1,2,…,m;j =1,2,…,n},E(Fm Sn) = {wui | i =1,2,…,m}∪{uivij | i =1,2,…,m;j =1,2,…,n}∪{uiui+1 | i =1,2,…,m-1}.　　本文得到了Fm Sn 的边色数和邻强边色数.     

图Fm(△)Fn的边色数和邻强边色数

V(Fm(△)Fn)={w}∪{ui|i=1,2,…,m}∪{vij|i=1,2,…,m;j=1,2,…,n},E(Fm(△)Fn)={wui|i=1,2,…,m}∪{uivij|i=1,2,…,m,j=1,2,…,n}∪{uiui+1|i=1,2,…,m-1}∪{vijvij+1|i=1,2,…,m;j=1,2,…,n-1}对图G的一个正常的k边染法f,若e∈E(G),e=uv,{f(uw)|uw∈E(G)}≠{f(uw)|uw∈E(G)}则称f为G的一个k-邻强边染色法,k的最小值称为G的邻强边色数.本文得到了Fm(△)Fn的边色数和邻强边色数.     

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

§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的一个边着色用了1,2,…,t中的所有颜色,并且关联于G的同一个顶点的边上的颜色各不相同,且这些颜色构成了一个连续的整数区间,则称这个边着色是G的区间t-着色。如果对某个正整数t,G有一个区间t-着色,则称G是可区间着色的。所有可区间着色的图构成的集合记作N。图G的亏度def(G)是粘在G的顶点上使它可区间着色的悬挂边的最小数目,显然,G∈N当且仅当def(G)=0。广义θ-链是把路P=[v_0,v_1,…,v_k](k≥1)的每一条边v_(i-1)v_i(i=1,2,…,k),用m_i≥2条两两内部不交的(v_(i-1),v_i)-路替换掉而得到的简单图,记作θ_(m_1,m_2,…,m_k)。把广义θ-图亏度的结论进行推广,确定了θ_(m_1,m_2,…,m_k)的亏度。     

图Fm(△)Sn的边色数和邻强边色数

对图G的一个正常的k边染色法f,若(≯)e∈E(G),e=uv,{f(uw)|uw∈E(G)}≠{f(vw)|vw∈E(G)},则称f为G的一个k-邻强边染色法,k的最小值称为G的邻强边色数.V(Fm(△)Sn)={w}∪{ui|i=1,2,…,m}∪{vij|i=1,2,…,m;j=1,2,…,n},E(Fm(△)Sn)={wui|i=1,2,…,m}∪{uivij|i=1,2,…,m;j=1,2,…,n}∪{uiui+1|i=1,2,…,m-1}.本文得到了Fm(△)Sn的边色数和邻强边色数.     

关于P_m×P_n的K-优美性

本文对 P_m×P_n 图的顶点 X_(ij)(i=1,2,…,m,j=1,2,…,n)作出标号:(i=1,2,…,m;j=2,3,…,n)式中,t=m(n—1)+n(m—1)+k—1。同时,证明了 P_m×P_n 图是 K优美的。因此,Gracl 猜想成为本文的特例而被证实。     

图F_m▽F_n的边色数和邻强边色数

V(Fm Fn)={w}∪{ui|i=1,2,…,m}∪{vij|i=1,2,…,m;j=1,2,…,n},E(Fm Fn)={wui|i=1,2,…,m}∪{uivij|i=1,2,…,m,j=1,2,…,n}∪{uiui+1|i=1,2,…,m-1}∪{vijvij+1|i=1,2,…,m;j=1,2,…,n-1}对图G的一个正常的k边染法f,若 e∈E(G),e=uv,{f(uw)|uw∈E(G)}≠{f(uw)|uw∈E(G)}则称f为G的一个k-邻强边染色法,k的最小值称为G的邻强边色数。本文得到了Fm Fn的边色数和邻强边色数。     

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

圈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中存在支配路.     

若干多重联图的边染色

设G1,G2,…,Gn是n个(n≥2)两两不相交的简单图,它们的n-重联图是在G1 G2 … Gn中,将Gi的每一顶点与Gj的每一顶点连接起来(i≠j,i,j=1,2,…,n)所得到的图,简记为K(G1,G2,…,Gn).若Gi≌G,i=1,2,…,n,则称K(G1,G2,…,Gn)为G的等n-重联图,简记为K(n,G).本文研究了若干多重联图的边染色.