关于交叉数为1的联图 王晶¹, 欧阳章东², 黄元秋³1. 长沙学院计算机工程与应用数学学院, 长沙 410003;
2. 湖南第一师范学院数学系, 长沙 410205;
3. 湖南师范大学数学与计算机科学学院, 长沙 410081 On the Join Graphs with Crossing Number One WANG Jing¹, OUYANG Zhangdong², HUANG Yuanqiu³1. College of Mathematics and Computer Science, Changsha University, Changsha 410003, China;
2. Department of Mathematics, Hunan First Normal University, Changsha 410205, China;
3. College of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China

摘要 图/表 参考文献 相关文章(5) 点击分布统计 下载分布统计 --> 全文: PDF(324 KB) HTML (1 KB) 输出: BibTeX | EndNote (RIS) 摘要确定图的交叉数是NP-完全问题.Kuratowski定理刻画了平面图的特征，而结合图的交叉数这一参数来研究非平面图的特征，目前相关结果甚少.本文从联图着手，研究当G1∨G2的交叉数为1时，刻画出因子图G1和G2须满足的充要条件. 服务 加入引用管理器 E-mail Alert RSS 收稿日期: 2016-06-24 PACS: O157.5 基金资助:国家自然科学基金（No.11371133），湖南省自然科学基金（No.14JJ3138）和湖南省教育厅优秀青年项目（No.16B028）资助项目. 引用本文: 王晶, 欧阳章东, 黄元秋. 关于交叉数为1的联图[J]. 应用数学学报, 2017, 40(5): 727-733. WANG Jing, OUYANG Zhangdong, HUANG Yuanqiu. On the Join Graphs with Crossing Number One. Acta Mathematicae Applicatae Sinica, 2017, 40(5): 727-733. 链接本文: http://123.57.41.99/jweb_yysxxb/CN/或 http://123.57.41.99/jweb_yysxxb/CN/Y2017/V40/I5/727 [1] Gross J L, Tucker T W. Topological Graph Theory. New York:Wiley, 1987 [2] Bondy J A, Murty U S R. Graph Theory, Graduate Texts in Mathematics. New York:Springer, 2010 [3] Bokal D, Oporowski B, Richter R B, Salazar G. Characterizing 2-crossing-critical graphs. Advances in Applied Mathematics, 2016, 74:23-208 [4] Pan S, Richter R B. The crossing number of K11 is 100. J. Graph Theory, 2007, 56(2):128-134 [5] McQuillan D, Pan S, Richter R B. On the crossing number of K13. J. Combinatorial Theory, Series B, 2015, 115:224-235 [6] Yang Y S, Lin X H, Lu J, Hao X. The crossing number of C(n;{1,3}). Discrete Mathematics, 2004, 289:107-118 [7] Ma D J, Ren H, Lu J J. The crossing number of the circular graph C(2m+2,m). Discrete Mathematics, 2005, 304:88-93 [8] Huang Y Q, Zhao T L. The crossing number of K1,4,n. Discrete Mathematics, 2008, 308:1634-1638 [9] Garey M R, Johnson D S. Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods, 1983, 4:312-316 [10] Kleitman D J. The crossing number of K5,n. J. Combin. Theory, 1970, 9:315-323 [11] Klešč M. The crossing numbers of Cartesian products of paths with 5-vertex graphs. Discrete Mathematics, 2001, 233:353-359 [12] Bokal D. On the crossing numbers of Cartesian products with paths. J. Combin. Theory, Series B, 2007, 97:381-384 [13] Ouyang Z D, Wang J, Huang Y Q. The crossing number of the Cartesian product of paths with complete graphs. Discrete Mathematics, 2014, 328:71-78 [14] 欧阳章东, 黄元秋. 关于 K2,2,2□Sn 的交叉数.应用数学学报, 2015, 38(6):968-975 (Ouyang Z D, Huang Y Q. On the Crossing Number of K2,2,2□Sn. Acta Mathematicae Applicatae Sinica, 2015, 38(6):968-975) [15] 吕胜祥, 黄元秋. K2,4□Sn 的交叉数.系统科学与数学, 2010, 30(7):929-935 (Lv S X, Huang Y Q. On the crossing number of K2,4□Sn. Journal of System Science and Mathematical Science, 2010, 30(7):929-935) [16] Oporowski B, Zhao D. Coloring graphs with crossings. Discrete Mathematics, 2009, 309:2948-2951 [17] Tang L, Wang J, Huang Y Q. The crossing number of the join of Cm and Pn. International J. Math. Com., 2007, 1:110-116 [18] Klešč M. The join of graphs and crossing numbers. Electronic notes in Discrete Mathematics, 2007, 28:349-355 [19] Klešč M, Schrötter Š. The crossing numbers of join products of paths with graphs of order four. Discussiones Mathematicae Graph Theory, 2011, 31:321-331 [20] Klešč M. The crossing numbers of join of the special graph on six vertices with path and cycle. Discrete Mathematics, 2010, 310:1475-1481 [21] Behzad M, Mahmoodian S E. On topological invariants of the product of graphs. Canad. Math. Bull., 1969, 12:157-166 [22] Klešč M, Petrillová J. On Cartesian products with small crossing numbers. Carpathian J. Math., 2012, 28:67-75 [23] Kulli V R, Muddebihal M H. Characterizations of join graphs with crossing number zero. Far East Journal of Applied Mathematics, 2001, 5:87-97 [24] Ouyang Z D. On the crossing number of a graph. Ph.D Thesis, Hunan Normal University, 2011 [25] Klešč M, Schrötter Š. The crossing numbers of join of paths and cycles with two graphs of order five. MMCP 2011, 2012, LNCS 7125:160-167 [26] Richter R B, Širáň J. The Crossing Number of K3,n in a surface. Journal of Graph Theory, 1996, 21:51-54 [1] 苏振华. 联图K1,1,1,2+Pn的交叉数[J]. 应用数学学报, 2017, 40(3): 345-354. [2] 李阳, 黄元秋. 联图S5 ∨ Cn的交叉数[J]. 应用数学学报, 2016, 39(2): 173-183. [3] 欧阳章东, 黄元秋. 关于K2,2,2□Sn的交叉数[J]. 应用数学学报, 2015, 38(6): 968-975. [4] 袁梓瀚, 黄元秋, 刘金旺. 循环图C(9,2)与路Pn的笛卡尔积的交叉数[J]. 应用数学学报(英文版), 2013, 36(2): 350-362. [5] 马刚, 马少仙, 张忠辅. 一些联图的均匀全染色[J]. 应用数学学报(英文版), 2010, 33(4): 624-631. PDF全文下载地址: http://123.57.41.99/jweb_yysxxb/CN/article/downloadArticleFile.do?attachType=PDF&id=14360 相关话题/应用数学 计算机 数学 统计 科学 领限时大额优惠券,享本站正版考研考试资料! 优惠券领取后72小时内有效，10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材，产品类型包含电子书、题库、全套资料以及视频，无论您是考研复习、考证刷题，还是考前冲刺等，不同类型的产品可满足您学习上的不同需求。 ... 考试优惠券 本站小编 Free壹佰分学习网 2022-09-19 物理所陈小龙研究团队荣获2020年度国家自然科学二等奖 11月3日，中共中央、国务院在北京人民大会堂隆重举行2020年度国家科学技术奖励大会，对为我国科学技术进步、经济社会发展、国防现代化建设做出突出贡献的科学技术人员和组织给予奖励，党和国家领导人出席奖励大会并为获奖科学家们颁奖。　　物理所“基于结构基元的新电磁材料和新效应的发现”项目荣获2020年度国 ... 中科院物理研究所 本站小编 Free考研考试 2021-12-27 物理所积极承办国家自然科学基金委交叉学部青年学术研讨会 2021年10月10-11日，由国家自然科学基金委交叉科学部主办、中国科学院物理研究所承办的第一届青年学术研讨会在北京怀柔召开。本次研讨会旨在为从事交叉科学研究的优秀青年科学家搭建学术交流平台，打破各学科间语言壁垒，促进交叉科学合作研究，助力青年人才成长，培养交叉科学文化。来自全国60余所高校及科研 ... 中科院物理研究所 本站小编 Free考研考试 2021-12-27 北京清洁能源前沿研究中心成立仪式暨第二期“栖湖物质科学论坛”顺利举办 2021年9月16日，北京清洁能源前沿研究中心成立仪式暨第二期“栖湖物质科学论坛”在物理所怀柔园区MA楼五层报告厅顺利举办。论坛邀请到物理所陈立泉院士做题为“电动中国：北京清洁能源前沿研究中心的使命”的报告。现场参加论坛活动的有工信部产业发展促进中心专项三处刘嘉副处长，物理所所长方忠院士、所务委员李 ... 中科院物理研究所 本站小编 Free考研考试 2021-12-27 中国科学院物理研究所自主研制无液氦稀释制冷机实现10mK以下极低温 稀释制冷机是当前超导量子计算、拓扑量子计算等国际上竞争异常激烈的量子信息技术研究必需的低温实验设备。　　中国科学院物理研究所是中国低温实验技术和低温物理研究的发源地，老一辈物理所人在70年代末就研制成功了我国第一台湿式稀释制冷机，实现了33mK的极低温（绝对零度以上0.033度）。面对新一轮量子信息 ... 中科院物理研究所 本站小编 Free考研考试 2021-12-27 中国科学院物理研究所举办2021年“公众科学日” 5月22日，中国科学院物理研究所第18届公众科学日活动在北京顺利举行。这场关于物理、关于科学的大型“狂欢”，吸引了数百万公众通过线上、线下的形式共同参与。　　本次公众科学日由中科院物理所与bilibili联合主办，中科院文献情报中心协办，主题是“中二所的奇妙冒险”，旨在打破物理与科学的次元壁，呈现妙 ... 中科院物理研究所 本站小编 Free考研考试 2021-12-27 怀柔园区“栖湖物质科学论坛”暨“栖湖咖啡馆”（第一期）学术研讨活动顺利举办 物理所怀柔园区第一期“栖湖物质科学论坛”暨“栖湖咖啡馆”学术研讨活动由怀柔研究部主办，于2021年5月4日下午在怀柔园区MA楼五层报告厅举办。论坛邀请中科院物理所向涛院士做了题为“超导物理前沿与展望”的报告，并邀请到北京大学量子材料中心主任王楠林教授、清华大学物理系凝聚态物理研究所所长张广铭教授、中 ... 中科院物理研究所 本站小编 Free考研考试 2021-12-27 物理所丁洪研究员获2020年度中国科学院杰出科技成就奖 近日，中国科学院公布了2020年度中国科学院杰出科技成就奖名单，我所丁洪研究员获得该奖项。　　中国科学院杰出科技成就奖授予院属单位在科技创新活动中做出重大成果的个人或集体，集体包括突出贡献者等主要完成人员，每年评选一次，每次授奖总数不超过10个。本奖项于2002年设立，2003年首次颁奖，2020年 ... 中科院物理研究所 本站小编 Free考研考试 2021-12-27 物理所碳化硅晶体生长和加工技术研发及产业化团队获得“2020年度中国科学院科技促进发展奖” 2020年1月15日，中国科学院2021年度工作会议在北京召开，会上宣读并表彰了中科院2020年度科技促进发展奖，物理所碳化硅晶体生长和加工技术研发及产业化团队获奖。　　中国科学院科技促进发展奖授予为推动中国科学院科学技术研究面向国家地方需求、经济社会发展，鼓励在服务国民经济、社会发展、社会公益等科 ... 中科院物理研究所 本站小编 Free考研考试 2021-12-27 物理所钱天研究员荣获2020年度中国科学院青年科学家奖 近日，中国科学院公布了2020年度中国科学院青年科学家奖获奖者名单，全院共有10名青年科技人才入选，我所钱天研究员位列其中。　　钱天研究员多年来利用角分辨光电子能谱实验手段从事凝聚态体系特别是拓扑材料电子结构的实验研究，取得了一系列重要的研究成果，包括在固体中首次实验证实外尔费米子和新型手性费米子， ... 中科院物理研究所 本站小编 Free考研考试 2021-12-27 2021“新年悟理”跨年科学演讲——“什么是相对论”成功开讲 12月30日晚，2021“新年悟理”跨年科学演讲在物理所M234报告厅举行。物理所研究员曹则贤现场开讲《什么是相对论》，为观众带来一场硬核的跨年科学盛宴。　　本次跨年科学演讲由中国科学院科学传播局、中国科学院物理研究所与长三角物理研究中心（中国溧阳）联合主办，中国科学报社、中国科学院大学协办。来自中 ... 中科院物理研究所 本站小编 Free考研考试 2021-12-27 Free考研考试FreeKaoYan.Com 欢迎来到Free考研考试，"为实现人生的Free而奋斗" 关于我们 联系我们 电子邮件 苏ICP备16059069号 © 2020 FreeKaoYan! . All rights reserved.