共查询到16条相似文献,搜索用时 78 毫秒
2.
3.
五阶图与星图的笛卡尔积交叉数 总被引:1,自引:0,他引:1
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. 相似文献
4.
5.
图G的交叉数,记作cr(G),是把G画在平面上的所有画法中边与边产生交叉的最小数目,它是拓扑图论中的一个热点问题。Kle?c和Petrillová刻画了当G1为圈且cr(G1G2)-2时,因子图G1和G2满足的充要条件。在此基础上,本文研究当|V(G1)|≥3且cr(G1G2)=2时,G1和G2应满足的充要条件。 相似文献
6.
7.
8.
苏振华 《数学的实践与认识》2017,(12):182-188
目前关于积图的交叉数的研究已经推广到六阶图与星图的积图.研究得到了一个特殊六阶图Q与n个孤立点nK_1的联图交叉数,然后通过收缩的方法,得到了Q与星图S_n的积图交叉数. 相似文献
9.
C(6,2)表示由圈C6增加边vivi 2(i=1,…,6,i 2(m od6))所得的图,把边vivi 2叫做C(6,2)的弦,B表示C(6,2)除去一条弦所得到的图,我们确定了B与Pn笛卡尔积的交叉数为5n-1. 相似文献
10.
确定图的交叉数是NP.完全问题.目前已确定交叉数的六阶图与星图的笛卡尔积图极少。本文确定了—个六阶图G与星图5k积图的交叉数为Z(6,n)+2n+[n/2]. 相似文献
11.
12.
13.
14.
Drago Bokal 《Journal of Graph Theory》2007,56(4):287-300
Zip product was recently used in a note establishing the crossing number of the Cartesian product K1,n □ Pm. 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 相似文献
15.
李丽萍 《数学的实践与认识》2014,(11)
目前已经确定的两个图的联图的交叉数结果较少.设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个顶点的路与圈. 相似文献
16.
把完全图$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$. 相似文献