W5×Sn的交叉数

确定图的交叉数是-个NP一完全问题.目前,对于六阶图与星图笛卡尔积的交叉数知之甚少.收稿证明了W5 X.Sn的交叉数为6[n/2][n-1/2] 2n 3[n/2]([x]表示不超过x的最大整数),并得到了W5的部分子图与Sn笛卡尔积的交叉数.     

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

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

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

六阶图Q与星图S_n的积图交叉数

目前关于积图的交叉数的研究已经推广到六阶图与星图的积图.研究得到了一个特殊六阶图Q与n个孤立点nK_1的联图交叉数,然后通过收缩的方法,得到了Q与星图S_n的积图交叉数.     

交叉数为2的笛卡尔积图

图G的交叉数,记作cr(G),是把G画在平面上的所有画法中边与边产生交叉的最小数目,它是拓扑图论中的一个热点问题。Kle?c和Petrillová刻画了当G₁为圈且cr(G₁G₂)-2时,因子图G₁和G₂满足的充要条件。在此基础上,本文研究当|V(G₁)|≥3且cr(G₁G₂)=2时,G₁和G₂应满足的充要条件。     

K_m~-□P_n的交叉数

Klesc等人先后确定了K_m~-□P_n(4≤m≤6)的交叉数,本文利用构造法确定了K_m-2K_2(4≤m≤12,m≠10,12)的交叉数.在此基础上,可进一步确定K_m~-□P_n(4≤m≤9,m≠8)的交叉数.相比而言,我们所采用的方法更具一般性.     

交叉数为2且因子图为路的笛卡尔积图

M.Kle??和J.Petrillová刻画了当G1为圈且cr (G1G2)=2时,因子图G1和G2所满足的充要条件.在此基础上,该文进一步刻画了在cr (G1G2)=2的前提下,当G1=P4,或者G1=P3且△(G2)=4时,因子图G2应满足的充要条件.     

Wm∨Pn的交叉数

在Klesc M给出的联图W_3 V P_n的交叉数的基础上,继续对联图Wm V Pn（m=4,5）的交叉数cr进行了研究,得到了cr（W3 V Pn）=Z（5,n）＋n＋「n/2＋1」以及cr（W5 V Pn）=Z（6,n）＋n＋3[n/2」＋1,n≥2.     

W_4 ∨ C_n的交叉数

本文研究了五阶图与圈图的联图交叉数.利用假设法和比较法等方法,得到了W4∨Cn的交叉数为Z(5,n)+n+n2+4,并推广了联图交叉数的结果与方法.     

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

On the crossing numbers of Cartesian products with trees

Zip product was recently used in a note establishing the crossing number of the Cartesian product K₁,n □ P_m. In this article, we further investigate the relations of this graph operation with the crossing numbers of graphs. First, we use a refining of the embedding method bound for crossing numbers to weaken the connectivity condition under which the crossing number is additive for the zip product. Next, we deduce a general theorem for bounding the crossing numbers of (capped) Cartesian product of graphs with trees, which yields exact results under certain symmetry conditions. We apply this theorem to obtain exact and approximate results on crossing numbers of Cartesian product of various graphs with trees. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 287–300, 2007     

K5×Sn的交叉数

By connecting the 5 vertices of K5 to other n vertices, we obtain a special family of graph denoted by Hn. This paper proves that the crossing number of Hn is Z(5, n) +2n+[n/2] 1, and the crossing number of Cartesian products of K5 with star Sn is Z(5, n) + 5n + [n/2]+1.     

Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method

The biplanar crossing number cr₂(G) of a graph G is min{cr(G₁) + cr(G₂)}, where cr is the planar crossing number. We show that cr₂(G) ≤ (3/8)cr(G). Using this result recursively, we bound the thickness by Θ(G) ‐ 2 ≤ Kcr₂(G)^0.4057 log₂n with some constant K. A partition realizing this bound for the thickness can be obtained by a polynomial time randomized algorithm. We show that for any size exceeding a certain threshold, there exists a graph G of this size, which simultaneously has the following properties: cr(G) is roughly as large as it can be for any graph of that size, and cr₂(G) is as small as it can be for any graph of that size. The existence is shown using the probabilistic method. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

S_n+W_n的邻点强可区别全色数

设G(V,E)是阶数不小于3的简单连通图,k是自然数,f是从V(G)∪E(G)到1,2,…,k的映射,满足:对任意的uv∈E(G),f(u)≠f(v),f(u)≠f(uv)≠f(v);对任意的uv,uw∈E(G)(v≠w),f(uv)≠f(uw);对任意的uv∈E(G),C(u)≠C(v),其中C(u)={f(u)}∪{f(v)uv∈E(G)}∪{f(uv)uv∈E(G)},则称f是图G的一个邻点强可区别的全染色法,简记作k-AVSDTC,且称χast(G)=min{k G的所有k-AVSDTC}为G的邻点强可区别的全色数.得到了星与轮联图的邻点强可区别的全色数.     

完全二部图K3,3与星Sn的积图的交叉数

确定图的交叉数是NP-完全问题．目前有关完全二部图与星图的积图的交叉数结果并不多．引入了一些新的收缩技巧,建立了积图K3,3□Sn与完全三部图K3,3□Sn之间的交叉数关系．从而,为进一步完全确定积图K3,3□Sn的交叉数提供了一条新途径．     

六阶图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.     

The crossing number of Cm × Cn is as conjectured for n ≥ m(m + 1)

It has been long conjectured that the crossing number of C_m × C_n is (m?2)n, for all m, n such that n ≥ m ≥ 3. In this paper, it is shown that if n ≥ m(m + 1) and m ≥ 3, then this conjecture holds. That is, the crossing number of C_m × C_n is as conjectured for all but finitely many n, for each m. The proof is largely based on techniques from the theory of arrangements, introduced by Adamsson and further developed by Adamsson and Richter. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 53–72, 2004     

星形图乘积的pebbling数

图 G的 pebbling数 f(G)是最小的整数 n,使得不论 n个 pebble如何放置在 G的顶点上 ,总可以通过一系列的 pebbling移动把一个 pebble移到任意一个顶点上 ,其中的 pebbling移动是从一个顶点上移走两个 pebble而把其中的一个移到与其相邻的一个顶点上 .设 K1,n为 n+1个顶点的星形图 .本文证明了 (n+2 )(m+2 )≥ f K1,n× K1,m)≥ (n+1) (m+1) +7,n>1,m>1.