修正冒泡排序网络的边偶泛圈性

对于一个二部图G,如果在G中存在任意长为偶数l(4≤l≤|V(G)|)的圈,则称这个二部图G是偶泛圈的:如果对G中任意一边e,在G中存在任意长为偶数l(4≤l≤|V(G)|)且包含e的圈,则称这个二部图G是边偶泛圈的.修正冒泡排序网络是互连网络中的一个重要的Cayley图模型.在此,证明了对任意的自然数n,当n≥3时,修正冒泡排序网络Y_n是偶泛圈的,同时也是边偶泛圈的.     

关于简单MCD图

设G是阶为n的简单图，若G中没有两个等长圈且具有最大可能的边数，则称G为简单MCD图。本文通过引进路分解概念给出了两个关于图中圈数的结果并应用它们证明了下述定理：若G是简单MCD图，则G不是2连通可平面图且对所有整数n，除七个例外，G不是阶为n的含有同胚于K4的2连通图。     

Hamiltonian图的泛圈性一个充分条件

根据Bondy在[4]中的想法：几乎任何一个Hamiltonian图的非平凡的充分条件都可能蕴含着图的泛圈性质,自然有如下猜测,设图G满足定理A的条件,则G是泛圈图或者n=2t,G=Kt,t.[2]证明了这一猜测在t=3时成立,[3]对t=4得到子了一个更强的结果,本文证明此猜测对一般情形(t≥3)均成立。     

给定匹配数和独立数时图零度的上界

设G是一个有n个点的简单图,分别记η(G),m(G)和α(G)为图G的零度、匹配数和独立数.设θ(G)是一个非负整数,定义为使图G成为二部图至少需要从G的边集中删去的边数.本文运用二部划分运算,证明了对于有n个点并且不含有圈长为2的倍数的圈为子图的简单图G,有η(G)≤n-2m(G)+20(G)和η(G)≤2α(G)+2θ(G)-n.     

关于几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m＜n)使对每个l∈{3,4,…,n} -{m},G恰有一个长为l的圈且不含长为m的圈,则称G是几乎唯一泛圈图,用(?)k表示具有n k条边和恰有1/2(k 1)(k 2)个圈的简单H图的集合,用(?)_k~*表示具有n k条边恰有2~k k个圈的简单外可平面H图的集合,本文确定了(?)_k和(?)_k~*中所有几乎唯一泛圈图,并证明这些图都是简单MCD图,本文还构造了50个含有同胚于K_4的子图的几乎唯一泛圈图,并提出了若干问题和猜想。     

Bondy的泛圈图定理的改进

记G=(V,E)是简单图,1971年Bondy得到O re条件下的泛圈图的著名结果:若2连通n阶图G的不相邻的任两点x、y均有d(x) d(y)≥n,则G是泛圈图或G=Kn/2,n/2.这里进一步研究条件d(x) d(y)≥n-1,得到:若2连通n阶图G的不相邻的任两点x、y均有d(x) d(y)≥n-1,则G是泛圈图或G∈{K(Cn 1)/2∨G(n-1)/2,Kn/2,n/2}.本文作者得知最近国际著名权威专家Ho lton等人也得到完全相同的结果,但本证明更简捷.     

一类几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m相似文献   

六阶图C_6+3K_2与P_n,C_n的联图交叉数

用P_n表示n个点的路,C_n表示长为n的圈,C_6+3K_2表示圈C_6添加三条相邻的边3K_2=C_3得到的图.在Kleitman给出的完全二部图的交叉数cr(K_(6,n))=Z(6,n)的基础上,得到了特殊六阶图C_6+3K_2与路P_n,圈C_n的联图交叉数分别为Z(6,n)+3[n/2]+2与Z(6,n)+3[n/2]+4.     

Hamiltonian[k,k+1]-因子

本文考虑n/2-临界图中Hamiltonian[k,k+1]-因子的存在性。Hamiltonian[k,k+1]-因子是指包含Hamiltonian圈的[k,k+1]-因子;给定阶数为n的简单图G,若δ(G)≥n/2而δ(G\e)相似文献   

关于图与圈之并图的圈唯一性

Farrell[1]引进图 G 的圈多项式 c(G;■).文[6]猜测:轮形图 W_8是圈唯一的.本文中我们证明上述猜测为真且讨论了某些图与圈之并图的圈唯一性.     

W6*Sn的交叉数

早在20世纪50年代,Zarankiewicz 猜想完全2-部图K_{m,n}(m\leq n)的交叉数为\lfloor\frac{m}{2}\rfloor\times \lfloor\frac{m-1}{2}\rfloor\times\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor (对任意实数x,\lfloor x\rfloor表示不超过x的最大整数). 目前这一猜想的正确性只证明了当m\leq6时成立. 假定著名的Zarankiewicz的猜想对m=7的情形成立,确定了6-轮W_{6}与星S_{n}的笛卡尔积图的交叉是 cr(W_{6}\times S_{n})=9\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor+2n+5\lfloor\frac{n}{2}\rfloor.     

Upper embeddability,edge independence number and girth

Combined with the edge-connectivity, this paper investigates the relationship between the edge independence number and upper embeddability. And we obtain the following result: Let G be a k-edge-connected graph with girth g. If α '(G)≤((k-1)2+2) [g/2]+(1-(-1)n)/2((k-1)(k-2)+1)-1,where k=1,2,3, and α(G) denotes the edge independence number of G, then G is upper embeddable and the upper bound is best possible. And it has generalized the relative results.     

一个特殊6点图Q与nK_1,P_n及C_n的联图交叉数

图的交叉数是图的一个重要参数,研究图的交叉数问题是拓扑图论中的前沿难题.确定图的交叉数是NP-难问题,因为其难度,能够确定交叉数的图类很少.通过圆盘画法途径,确定了一个特殊6点图与n个孤立点nK_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+2[n/2],cr(Q+P_n)=Z(6,n)+2[n/2]+1及cr(Q+C_n)=Z(6,n)+2[n/2]+3.     

$K_{5}\times S_{n}$ 的交叉数

把完全图$K_{5}$的五个顶点与另外$n$个顶点都联边得到一类特殊的图$H_{n}$.文中证明了$H_{n}$的交叉数为$Z(5,n)+2n+\lfloor \frac{n}{2}\rfloor+1$,并在此基础上证明了$K_{5}$与星$K_{1,n}$的笛卡尔积的交叉数为$Z(5,n)+5n+\lfloor\frac{n}{2} \rfloor+1$.     

联图$K_5+P_n$的交叉数

A join graph denoted by G + H,is illustrated by connecting each vertex of graph G to each vertex of graph H.In this paper,we prove the crossing number of join product of K_5 + P_n is Z(5,n) + 2 n + [n/2] + 4 for n ≥ 2.     

五阶图与星图的笛卡尔积交叉数

In this paper, we compute the crossing number of a specific graph Hn, and then by contraction, we obtain the conclusion that cr（G13 × Sn） = 4[n/2] [n-1/2]＋[n/2] . The result fills up the blank of the crossing numbers of Cartesian products of stars with all 5-vertex graphs presented by Marian Klesc.     

图的距离无符号拉普拉斯谱半径的关于色数的下界

Let G be a connected graph on n vertices with chromatic number k, and let ρ(G)be the distance signless Laplacian spectral radius of G. We show that ρ(G) ≥ 2n + 2「n k」- 4,with equality if and only if G is a regular Tur′an graph.     

On the second eigenvalue and random walks in randomd-regular graphs

The main goal of this paper is to estimate the magnitude of the second largest eigenvalue in absolute value, λ₂, of (the adjacency matrix of) a randomd-regular graph,G. In order to do so, we study the probability that a random walk on a random graph returns to its originating vertex at thek-th step, for various values ofk. Our main theorem about eigenvalues is that $$E|\lambda _2 (G)|^m \leqslant \left( {2\sqrt {2d - 1} \left( {1 + \frac{{\log d}}{{\sqrt {2d} }} + 0\left( {\frac{1}{{\sqrt d }}} \right)} \right) + 0\left( {\frac{{d^{3/2} \log \log n}}{{\log n}}} \right)} \right)^m $$ for any \(m \leqslant 2\left\lfloor {log n\left\lfloor {\sqrt {2d - } 1/2} \right\rfloor /\log d} \right\rfloor \) , where E denotes the expected value over a certain probability space of 2d-regular graphs. It follows, for example, that for fixedd the second eigenvalue's magnitude is no more than \(2\sqrt {2d - 1} + 2\log d + C'\) with probability 1?n ^?C for constantsC andC′ for sufficiently largen.     

K2,4×Sn的交叉数

Garey和Johnson证明了确定图的交叉数是一个NP-完全问题.确定了笛卡尔积图$K_{2,4}\times S_{n}$的交叉数是$Z(6,n)+4n.$ 当$m\geq 5,$猜想${\rm cr}(K_{2,m}\timesS_{n})={\rm cr}(K_{2,m,n})+n\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor$.