应用数学学报
應用數學學報
응용수학학보
ACTA MATHEMATICAE APPLICATAE SINICA
2008年
4期
615-623
,共9页
交叉数%轮图%星图%笛卡尔积
交扠數%輪圖%星圖%笛卡爾積
교차수%륜도%성도%적잡이적
确定图的交叉数是-个NP一完全问题.目前,对于六阶图与星图笛卡尔积的交叉数知之甚少.收稿证明了W5 X.Sn的交叉数为6[n/2][n-1/2]+2n+3[n/2]([x]表示不超过x的最大整数),并得到了W5的部分子图与Sn笛卡尔积的交叉数.
確定圖的交扠數是-箇NP一完全問題.目前,對于六階圖與星圖笛卡爾積的交扠數知之甚少.收稿證明瞭W5 X.Sn的交扠數為6[n/2][n-1/2]+2n+3[n/2]([x]錶示不超過x的最大整數),併得到瞭W5的部分子圖與Sn笛卡爾積的交扠數.
학정도적교차수시-개NP일완전문제.목전,대우륙계도여성도적잡이적적교차수지지심소.수고증명료W5 X.Sn적교차수위6[n/2][n-1/2]+2n+3[n/2]([x]표시불초과x적최대정수),병득도료W5적부분자도여Sn적잡이적적교차수.
