二分图中关于Enomoto问题的结果

设k,n1和n2是3个正整数,G=（V1,V2;E）是一个二分图,使得｜V1｜=n1,｜V2｜=n2,其中n1≥2k＋1,n2≥2k＋1并且n1-n2≤1．如果对任意不相邻的x∈V1和y∈V2,都有d（x）＋d（y）≥2k＋2,则G包含k个相互独立的圈．以上结果部分地回答了Enomoto提出的关于二分图有独立圈的问题．     

度和与图中具有给定阶数的点不交的路

设G是一个n阶图，n=∑^ki=1ni，其中,ni≥2(i=1,2,…，k）是整数。我们利用度和给出图G中存在n1,n2，…，nk阶点不交路的充分条件。     

与4/p = 1/(n1) + 1/(n2) + 1/(n3) 相关的素变量均值估计

如果n是正整数,我们用f（n）表示丢番图方程4/p=1/n_1＋1/n_2＋1/n_3的正整数解（n1,n2,n3）的个数.对于素数p,f（p）可以分解为f1（p）＋f2（p）,这里fi（p）（i=1,2）为分母n1,n2,n3中恰有i个能被p整除的解的个数.本文我们将研究关于均值∑p〈xfi（p）,i=1,2,的估计,其中p表示素数.     

关于多项式系数的整除性

设 n是正整数 ,k1 ,k2 ,… ,ks 是适合 k1 +k2 +… +ks=n的非负整数 ,正整数 nk1 k2 … ks=n!k1 !k2 !… ks!称为多项式系数 .本文讨论了当n=a0 +a1 p+a2 p2 +… +arpr ,其中 p为素数且 p≤ n,0≤ ai相似文献   

有向循环图的支撑树数

设k≥2,1≤a_1相似文献   

太阳图与路的笛卡儿积图的任意可分性（英文）

一个阶为n的图G称为是任意可分的(简作AP),如果对于任一正整数序列τ=(n₁,n₂,…,n_k)满足n=n₁+n₂+…+n_k,总是存在顶点集V(G)的一个划分(V₁,V₂,…,V_k)满足:对于i∈[1,k],|V_i|=n_i,且子图G|V_i|是图G的V_i导出的一个连通子图.我们用S~*=S(n;m₁,m₂,…,m_n)来表示最大度△(S~*)=3的太阳图.本文讨论了图S~*P_m(m≥3)的任意可分性.     

完全r部图Kr（t）的{=C3，C2k}-强制分解（k≥4）的渐近存在性

研究基于顶点集V=Ui=1^rVi（其中｜Vi｜=t，i=1，2，……，r）的完全r部图Kr（t）的3圈和2k圈{C3，C2k}-强制分解（k≥4）的存在性问题．通过构造并运用Kr（t）的两种分解法，证明了Kr（t）的〈C3，C2k}-强制分解（k≥4）的渐近存在性，即对于任意给定的正整数k≥4，存在常数r0（k）=5k＋2，使得当r≥r0（k）时，Kr（t）的{C3，C2k}-强制分解存在的必要条件也是充分的．     

广义Peterson图的邻点可区别的全染色

设P_(n,k)是一个简单图,其顶点集和边集分别为:V(P_(n,k))={u_0,u_1,…u_(n-1),v_0,v_1,…v_(n-1)},E(P_(n,k))={u_iu_(i+1),u_iv_i,v_iv_(1+k)},则称P_(n,k)为广义Peterson图,其中n≥5,0相似文献   

关于完全t部图的色唯一性

设P(G,λ)是图的色多项式。如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.这里通过比较t 1色类的色划分数目,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,当min(n1,n2,…,nt)充分大时,完全t部图K(n1,n2,…,nt)是否是色唯一图?)。改进了文献[5]中的结果。证明了若Σ1≤i≤ta2i=T,min{n a1,n a2,…,nt at,n-1}≥(T 1)/2,则K(n a1,n a2,…,n at)是色唯一图(其中ai是实数,n ai是正整数)。从而证明了若|ni-nj|≤k(i,j=1,2,…,t),min{n1,n2,…,nt}≥tk2/8 1,则K(n1,n2,…,nt)是色唯一图。     

二分（0，mf—m＋1）-图的正交（0，f）-因子分解

设G=（X,Y,E（G））是一个二分图,分别用V（G）=X∪Y和E（G）表示G的顶点集和边集．设f是定义在V（G）上的整数值函数且对任意x∈V（G）有f（x）≥k．设H1,H2,…,Hk是G的k个顶点不相交的子图,且｜E（Hi）｜=m,1≤i≤k．本文证明了每个二分（0,mf—m＋1）．图G有一个（0,f）-因子分解正交于Hi（i=1,2,…,k）     

Kp,q-factorization of complete bipartite graphs

Let K_(m,n) be a complete bipartite graph with two partite sets having m and nvertices, respectively. A K_(p,q)-factorization of K_(m,n) is a set of edge-disjoint K_(p,q)-factorsof K_(m,n) which partition the set of edges of K_(m,n). When p=i and q is a prime number,Wang, in his paper "On K_(1,k)-factorizations of a complete bipartite graph" (Discrete Math,1994, 126; 359-364), investigated the K_(1,q)-factorization of K_(m,n) and gave a sufficientcondition for such a factorization to exist. In the paper "K_(1,k)-factorizations of completebipartite graphs" (Discrete Math, 2002, 259: 301-306), Du and Wang extended Wang'sresult to the case that q is any positive integer In this paper, we give a sufficient conditionfor K_(m,n) to have a K_(p,q)-factorization. As a special case, it is shown that the Martin's BACconjecture is true when p: q=k: (k+1) for any positive integer k.     

On bipartite zero-divisor graphs

A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3.     

极大饱和图D（n,k）的极值性质及圈唯一性

本文证明了极大饱和图Ｄ（ｎ，ｋ）的一个极值性质：在与Ｄ（ｎ，ｋ）具有相同度序 所有图中，唯有Ｄ（ｎ，ｋ）含有最少的Ｋ３子图，并由此推出，在几乎正则图的范围内，ｋ个完全图之并及完全ｋ部多分图均是圈唯一的。本文还用图谱方法，证明了完全二分图Ｋｍ，ｎ的圈唯一性。     

图的{P4}——分解

一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上．记Pl长度为l-1的路，如果G能够分解成若干个Pl，则称G存在{Pl}——分解，关于图的给定长路分解问题主要结果有：（i）连通图G存在{P3}-分解当且仅当G有偶数条边（见[1]）；（ii）连通图G存在{P3，P4}-分解当且仅当G不是C3和奇树，这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树（见[3]）．本文讨论了3正则图的{P4}--分解情况，并构造证明了边数为3k（k∈Z且k≥2）的完全图Kn和完全二部图Kr,s存在{P4}-分解.     

Line graphs of complete multipartite graphs have small cycle double covers

It has been shown by MacGillivray and Seyffarth (Austral. J. Combin. 24 (2001) 91) that bridgeless line graphs of complete graphs, complete bipartite graphs, and planar graphs have small cycle double covers. In this paper, we extend the result for complete bipartite graphs, and show that the line graph of any complete multipartite graph (other than K_1,2) has a small cycle double cover.     

Ring graphs and complete intersection toric ideals

We study the family of graphs whose number of primitive cycles equals its cycle rank. It is shown that this family is precisely the family of ring graphs. Then we study the complete intersection property of toric ideals of bipartite graphs and oriented graphs. An interesting application is that complete intersection toric ideals of bipartite graphs correspond to ring graphs and that these ideals are minimally generated by Gröbner bases. We prove that any graph can be oriented such that its toric ideal is a complete intersection with a universal Gröbner basis determined by the cycles. It turns out that bipartite ring graphs are exactly the bipartite graphs that have complete intersection toric ideals for any orientation.     

若干图的卡氏积的距离谱和距离能量(英文)

G是顶点集为{v_1,v_2,…,v_n}的连通简单图,G_1,G_2,…,G_n是有限图。联并图G[G_1,G_2,…,G_n】是按如下方式在G_1UG_2U…UG_n上加边而成的图:在G_i和G_j之间的任何两个顶点间加边,若v_i和v_j在G中相邻.[7]给出了两个距离正则图的卡氏积的距离谱.本文计算了联并图和距离正则图的卡氏积及两个联并图的卡氏积的距离谱.在此基础之上,我们得到了两个利用联并图与非同谱距离正则等能量图作卡氏积及联并图作卡氏积构造非同谱等距离能量图族的方法.     

关于分数因子两个开问题的解答

本文指出极小连通二部分数1-因子不一定是极小2-连通图.研究了σ₂（G）与分数k-因子存在性之间的关系,指出存在一个特例在满足阶数n≥4k-5,δ（G）≥k且σ₂（G）≥n条件下,图G不存在分数k-因子.     

K3-free图的线图的哈密顿性

设G是一个简单图，Gi G，G1在G中的度定义为d（Gt）=∑v∈v（c）d（v），其中d（v）为v在G中的度数。本文的主要结果是：设G是n≥2阶几乎无桥的简单连通K3-free图，且G≌k1,n-1、Q1和Q2，若对G中任何同构于四个顶点路的导出子图I有d（I）≥n＋2，则G有一个D-闭迹，从而G的线图L（G）是哈密顿图。     

(n,k)-排列图的条件连通度(英文)

点连通度是衡量互联网络容错性的一个重要参数.尽管点连通度能正确地反映了系统的容错性能,但是不能正确反映大规模网络的健壮性能.条件连通度通过对各分支附加一些要求(当整个网络被破坏时)来克服这个缺点.给定一个基于图G的网络和一个正整数l,G的R~l-连通度,记为k~l(G),定义为图G的最小节点子集的节点数,使其去掉后,G是不连通的,且每个分支的最小度至少是l.在本文中,我们得到了(n,k)-排列图的条件连通度k~l(A(_n,k))=[(l+1)k-l](n-k)-l,其中k≥l+2,n≥k+l.