关于交叉数为2的联图

确定图的交叉数是NP-完全问题.Kuratowski定理刻画了平面图的结构特征,而对于交叉数为k(k≥1)的非平面图G的结构特征刻画,目前相关结果甚少.对于交叉数为1的联图G_1∨G_2,我们已经刻画出因子图G_1和G_2满足的充要条件.本文刻画了当△(G_2)≠3且cr(G_1∨G_2)=2时因子图G_1和G_2须满足的充要条件.     

关于Hamilton3-正则2-连通平面图的一个注记

设Fk*是满足以下条件的3-正则2-连通平面图G所组成的图类,在G中存在这样的圈C,使得G-E(C)产生k个不相交的树T1,…,Tk(|E(Ti)|≥3,i=1,…,k),且这些树是按C的指定方向C*依次粘在圈C上的．本文主要证明了如下结果:Fk*中的图都是Hamilton的．     

变更图的直径

P(t,n)和C(t,n)分别表示在阶为n的路和圈中添加t条边后得到的图的最小直径；f(t,k)表示从直径为k的图中删去t条边后得到的连通图的最大直径．这篇文章证明了t≥4且n≥5时,P(t,n)≤(n-8)/(t 1) 3；若t为奇数,则C(t,n)≤(n-8)/(t 1) 3；若t为偶数,则C(t,n)≤(n-7)/(t 2) 3．特别地,「(n-1)/5」≤P(4,n)≤「(n 3)/5」,「n/4」-1≤C(3,n)≤「n/4」．最后,证明了：若k≥3且为奇数,则f(t,k)≥(t 1)k-2t 4．这些改进了某些已知结果．     

六阶图G与Sn的积图的交叉数

确定图的交叉数是NP．完全问题．目前已确定交叉数的六阶图与星图的笛卡尔积图极少。本文确定了—个六阶图G与星图5k积图的交叉数为Z（6,n）＋2n＋[n/2].     

7阶循环图C(7,2)与Pn的笛卡儿积的交叉数

C(7,2)表示由圈C7(v1v2…V7v1)增加边vivi 2(i=1,2,…,7,i 2(rood 7))所得的循环图.目前没有有关七阶图与路、星和圈的笛卡尔积交叉数的结果,我们证明了7阶循环图C(7,2)与路Pn的笛卡儿积的交叉数是8n.     

带弦圈的最小2宽直径

设k为正整数,G是简单k连通图.图G的k宽直径,dk(G),是指最小的整数ι使得对任意两不同顶点x,y∈V(G),都存在k条长至多为ι的内部不交的连接x和y的路.用C(n,t)表示在圈Gn上增加t条边所得的图.定义h(n,t):min{d2(C(n,t))}.本文给出了h(n,2)=[n/2].而且,给出了当t较大时h(n,t)的界.     

临界h-边-连通图的临界度

图G称为k-临界h-边-连通的,若h=λ(G)且对每个k顶点集{u1,…,uk}有λ(G-{u1,…,ui})≤λ(G-{u1,…,ui-1})-1,I≤k.若G是k-临界h-边-连通但不(k 1)-临界h-边-连通,则记之为(h*,k*)λ.本文证明了:存在(h*,k*)λ图的充要条件是(1)1≤k≤[(h 1)/2],h≡0,1,2(mod 4);1≤k≤[(h-1)/2],h≡3(mod 4);或(2)k=h,G=Kk 1.     

循环图C(10,2)与路P_n的笛卡尔积的交叉数

证明了循环图C(10,2)与路P_n的笛卡尔积的交叉数是10n及循环图C(2m,2)的一点悬挂和两点悬挂的交叉数分别是m,2m.     

关于Q(√/4k2x+1)的理想类群的循环子群

设d,a,k,n是适合4k2n+1 =da2, k>1, n>2, d无平方因子的正整数;又设C(K)和h(K)分别是实二次域K=Q(√d)的理想类群和类数.本文证明了:当a<0.5k0.56n时,则h(K)≡0(mod n)和C(K)必有n阶循环子群.     

完全多部图K_(1*r,3*(k-2))的m数

如果对一个图G的每个顶点v,任给一个k-列表L(v),使得G要么没有正常列表染色,要么至少有两种正常列表染色,则称图G具有M(k)性质.定义图G的m数为使得图G具有M(k)性质的最小整数k,记为m(G).已有研究表明,当k=3,4时,图K_(1*r,3*(k-2))具有M(k)性质,且当r≥2时,m(K_(1*r,3*(k-2)))=k.本文将上述结论推广到每一个k,证明了对任意r∈N~+,k≥3,图K_(1*r,3*(k-2))具有M(k)性质,且当k≥4,r≥(k-2)时,m(K_(1*r,3*(k-2)))=k.此外,得到图K_(1,3,3,3)的m数为4,该图是图K_(1*r,3*(k-2))中r=1,k=5时的特殊情况,同时也是现有研究中尚未解决的一个问题.     

一类非凸的不可定向交叉数的序列

It is well known that finding the crossing number of a graph on nonplanar surfaces is very difficult.In this paper we study the crossing number of the circular graph C（10,4） on the projective plane and determine the nonorientable crossing number sequence of C（10,4）.On the basis of the result,we show that the nonorientable crossing number sequence of C（10,4） is not convex.     

关于同余式$\sigma(n)\equiv 1\pmod n$

Let k ≥ 2 be an integer, and let σ(n) denote the sum of the positive divisors of an integer n. We call n a quasi-multiperfect number if σ(n) = kn + 1. In this paper, we give some necessary properties of them.     

三边连通超欧拉图的一个注记

For two integers l 0 and k ≥ 0,define C(l,k) to be the family of 2-edge connected graphs such that a graph G ∈ C(l,k) if and only if for every bond S-E(G) with |S| ≤ 3,each component of G-S has order at least(|V(G)|-k)/l.In this note we prove that if a 3-edge-connected simple graph G is in C(10,3),then G is supereulerian if and only if G cannot be contracted to the Petersen graph.Our result extends an earlier result in [Supereulerian graphs and Petersen graph.JCMCC 1991,9:79-89] by Chen.     

关于同余式$\sigma(n)\equiv 1\pmod n$, II

Let k ≥ 2 be an integer, and let a（n） denote the sum of the positive divisors of an integer n. We call n a quasi-multiperfect number if a（n） = kn ＋ 1. In this paper, we give some necessary properties of quasi-multiperfect numbers with four different prime divisors.     

一个关于近-三角剖分嵌入的内插定理

一个近三角剖分嵌入是指一个图嵌入在一个曲面上,使得至多可能有一个面不是三角面。在本文中我们证明了如下结果：如果一个图G在某个可定向曲面S_h上有三角剖分嵌入,那么G在S_k上有一个近三角剖分嵌入,这里k=h,h 1,…,[β(G)/2],而β(G)是图G的Betti数。     

无向超环面网$C(3,3,\ldots,3)$的$(n,2n)$控制数

$(d,k)$控制数是用来刻画容错网络中资源共享可靠性的一个新参数. 本文证明：$n\, (n\geq 3)$维无向超环面网$C(3,3,\ldots,3)$的$(n,2n)$控制数为 $3$.     

High dimensional reducible hyperplane sections with multigenera $\leq$ 1

Let X be an algebraic submanifold of the complex projective space $\mathbb{P}^N$ of dimension $n \geq 5$. We describe those $X \subset \mathbb{P}^N$ whose intersection with some hyperplane is a smooth simply normal crossing divisor $A_{1} + \cdots + A_{r}$ with $r \geq 2$ such that $g(A_{k}, L_{A_k}) \leq 1$ for $k=1,\ldots, r$.Received: 14 December 2001     

关于完全三部图色唯一性的一个注记

Let P(G,λ) be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P(H,λ) = P(G,λ) implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 31m2 + 31k2 + 31mk+ 31m? 31k+ 32√m2 + k2 + mk, where n,k and m are non-negative integers, then the complete tripartite graph K(n - m,n,n + k) is chromatically unique (or simply χ-unique). In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 31m2 + 31k2 + 31mk + 31m - 31k + 43, then the complete tripartite graph K(n - m,n,n + k) is χ-unique, which is an improvement on Zou Hui-wen's result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture.     

$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$.