星图S_4的交叉数  

Crossing number of Star graph S_4

作　　者：吕波[1] 徐喜荣[1] 杨元生[1] 张科[1] 郑百功[1] 

机构地区：[1]大连理工大学电子信息与电气工程学部计算机科学与技术学院,辽宁大连116024

出　　处：《大连理工大学学报》2014年第4期469-476,共8页Journal of Dalian University of Technology

基　　金：国家自然科学基金资助项目(61170303;60973014;10671191)

摘　　要：研究网络拓扑结构图星图S4的交叉数问题.首先构造星图S4好的画法,得到了S4交叉数的上界,然后给出了S4交叉数下界的数学证明,最终得到S4的交叉数的精确值为8.同时给出了与其具有同构关系的图S4,3和图A4,3的交叉数.The problem of the crossing number about network topological structure graph S4 is studied.Firstly,by constructing a good drawing of Star graph S4 ,an upper bound of the crossing number of S4 is obtained.Then,the lower bound of the crossing number of S4 is obtained by mathematical proof.Lastly,the conclusion is drawn that the exact value of the crossing number of S4 is 8.Meanwhile,the crossing numbers of graph S4,3 and graph A4,3 ,which are isomorphic to S4 ,are given.

关 键 词：交叉数 画法 Star图 (n k)-Star图 Arrangement图 

分 类 号：O157.9[理学—数学] TP302[理学—基础数学]