关于一个特殊六阶图与路和圈的联图的交叉数

Garey和Johnson证明了确定图的交叉数问题是一个NP-难问题.目前,已确定交叉数的图类并不多.本文证明了一个特殊6阶图与n个孤立点,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+n;cr(Q+P_n)=Z(6,n)+n+1及cr(Q+C_n)=Z(6,n)+n+3.     

一个五阶图与路、圈的联图的交叉数

目前已经确定的两个图的联图的交叉数结果较少.设H是由一个4圈及一个孤立点所构成的5阶图.研究了图H与路、圈的联图的交叉数,得到了cr(H+P_n)=Z(5,n)+[n/2]+l,cr(H+C_n):Z(5,n)+[n/2]+2,其中,P_n与C_n分别表示含n个顶点的路与圈.     

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

K_4∨C_n的交叉数

在KlescM给出的完全图K_4∨P_n的交叉数的基础上,得到了cr(K_4∨C_n)=Z(4,n)+n+4,n≥3.特别地,当n=3时,cr(K_4∨C_3)=cr(K_7)=9,由此得到完全图K_7的交叉数另一种证明方法.     

联图S_5∨C_n的交叉数

两个图G和H的联图,记作G∨H,是指将G中每个点与H中的每个点连边得到的图.本文证明了星图S_5与圈C_n的联图S_5∨C_n的交叉数为Z(6,n)+4[n/2]+3(n≥3),其中Z(m,n)=[m/2][(m-1)/2][n/2][(n-1)/2],m,n为非负整数.     

联图K_(1,1,1,2)+P_n的交叉数

确定图的交叉数是一个NP-完全问题.目前大多数的五阶图与路的联图交叉数已经确定,但是仍有少数复杂的五阶图与路的联图交叉数没有确定.本文深化这方面的研究,在Kleitman给出的完全二部图的交叉数cr(K_(5,n))=Z(5,n)和Ho得到的完全多部图的交叉数cr(K_(1,1,1,2,n))=Z(5,n)+2n的基础上,根据图的结构特点,证明了联图K_(1,1,1,2+P_n的交叉数为Z(5,n)+2n+2.     

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.     

五阶图与路P_n的联图交叉数

利用Kleitman D J给出的完全二部图的的交叉数cr(_(5,n))=Z(5,n)的结果,分别得到了联图G_(12)∨P_n,G_(15)∨P_n,G_(18)∨P_n的交叉数.同时,给出了目前已知的所有五阶图与路的联图交叉数情况.     

一个6点图与路的联图的交叉数

一个图G的交叉数cr(G)是把图G画在平面上,在所有画法中所产生的最少的交叉数.由于其结构的特殊性,能够确定两个图的联图交叉数的精确值的图类很少.本文通过圆盘画法这一途径,确定了一个特殊6点图与路P_n的联图的交叉数.     

K_(2,4)×S_n的交叉数

将K_(2,4)的6个顶点与n个点相连,得到的图记为H_n.先证明了H_n的交叉数为Z(6,n)+2n,然后证明了K_(2,4)×S_n的交叉数为Z(6,n)+4n.     

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

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.     

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.     

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

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

ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K1,8,n

The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph K_m,n (m≤ n) is Z(m,n), where Z(m,n)=\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor\lfloor\frac{n}{2}\rfloor$\lfloor\frac{n-1}{2}\rfloor$ (for any real number x, $\lfloor x\rfloor$ denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m≤ 6. In this article, the authors prove that if Zarankiewicz' conjecture holds for m≤9, then the crossing number of the complete tripartite graph K_1,8,n is $Z(9, n)+ 12\lfloor\frac{n}{2}\rfloor$.     

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

有向圈的笛卡尔积有向图的双控制数

Let γ*(D) denote the twin domination number of digraph D and let Cm Cn denote the Cartesian product of C_m and C_n, the directed cycles of length m, n ≥ 2. In this paper, we determine the exact values: γ*(C_2?C_n) = n; γ*(C_3 ?C_n) = n if n ≡ 0(mod 3),otherwise, γ*(C_3?C_n) = n + 1; γ*(C_4?C_n) = n + n/2 if n ≡ 0, 3, 5(mod 8), otherwise,γ*(C_4?C_n) = n + n/2 + 1; γ*(C_5?C_n) = 2n; γ*(C_6?C_n) = 2n if n ≡ 0(mod 3), otherwise,γ*(C_6?C_n) = 2n + 2.     

图的无符号拉普拉斯和距离无符号拉普拉斯特征值

Let G be a simple graph. We first show that ■, where δiand di denote the i-th signless Laplacian eigenvalue and the i-th degree of vertex in G, respectively.Suppose G is a simple and connected graph, then some inequalities on the distance signless Laplacian eigenvalues are obtained by deleting some vertices and some edges from G. In addition, for the distance signless Laplacian spectral radius ρQ(G), we determine the extremal graphs with the minimum ρQ(G) among the trees with given diameter, the unicyclic and bicyclic graphs with given girth, respectively.     

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个$k$($k\geq 5$ 是一个整数) 连通图 $G$ 中,如果 $\delta(G)\geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $\delta(G)\geq k+1$,并且 $G$ 中既不含$K_{2}+(\lfloor\frac{k-1}{2}\rfloor K_{1}\cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$t\geq 3$),则当 $k\geq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.