如果一个图可以嵌入在平面内使得每条边最多被交叉一次,则称该图为1-可平面图.如果一个图可以嵌入在平面内使得任何两个交叉不共享关联点,则称该图为IC-可平面图.如果一个图可以嵌入在平面内使得任何两个交叉最多共享一个关联点,则称该图为NIC-可平面图.1-可平面图,IC-可平面图与NIC-可平面图是三类重要的超越可平面图,它们在模块网络,社交网络和生物网络上有着重要的应用.图的约束数是为了使图的支配数严格增加所需要删除的最少的边数,它是衡量网络脆弱性的一个重要参数.本文考虑1-可平面图,IC-可平面图与NIC-可平面图的结构,并利用得到的结构定理证明了它们的约束数分别最多是13,11与12.
Abstract
A graph that can be drawn in the plane so that each edge is crossed at most once, or any two crossings do not share a common incident vertex, or any two crossings share at most one common incident vertex is 1-planar, or IC-planar, or NIC-planar, respectively. 1-planar graphs, IC-planar graphs, and NIC-planar graphs are three famous classes among beyond-planar graphs, which have many applications to the modular networks, social networks and bio-networks. The bondage number of a graph is the minimum number of edges such that the removal of them from the graph makes the domination number increases. It is an useful parameter to measure the vulnerability of the network. In this paper, the structures of 1-planar graphs, IC-planar graphs, and NIC-planar graphs are described, which are later applied to prove that the bondage number of every 1-planar graph, IC-planar graph, and NIC-planar graph is at most 13, 11, and 12, respectively.
关键词
1-可平面图 /
IC-可平面图 /
NIC-可平面图 /
超越可平面图 /
约束数
{{custom_keyword}} /
Key words
1-planar graph /
IC-planar graph /
NIC-planar graph /
beyond-planar graph /
bondage number
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Didimo W, Liotta G, Montecchiani F. A survey on graph drawing beyond planarity. ACM Computing Surveys, 52(1):1-37
[2] Kobourov S G, Liotta G, Montecchiani F. An annotated bibliography on 1-planarity. Computer Science Review, 2017, 25:49-67
[3] 张欣, 刘维婵. 1-平面图及其子类的染色. 运筹学学报, 2017, 21(4):135-152
(Zhang X, Liu W C. The coloring of the class of 1-planar graphs and its subclasses. Operations Research Transactions, 2017, 21(4):135-152)
[4] Zhang X, Wang H J, Xu L. Equitable coloring of three classes of 1-planar graphs. Acta Mathematicae Applicatae Sinica, English Series, 2018, 34(2):362-372
[5] 张欣, 刘桂真, 吴建良. 1-平面图的结构性质及其在无圈边染色上的应用. 中国科学:数学, 2010, 40(10):1025-1032
(Zhang X, Liu G Z, Wu J L. Structural properties of 1-planar graphs and an application to acyclic edge coloring. SCIENTIA SINICA:Mathematica, 2010, 40(10):1025-1032)
[6] Bauer D, Harary F, Nieminen J, Suffel C L. Domination alteration sets in graphs. Discrete Mathematics, 1983, 47(C):153-161
[7] Fink J F, Jacobson M S, Kinch L F, Roberts J. The bondage number of a graph. Discrete Mathematics, 1990, 86(1):47-57
[8] Kang L, Yuan J. Bondage number of planar graphs. Discrete Mathematics, 2000, 222(1-3):191-198
[9] Huang J, Xu J M. The bondage numbers of graphs with small crossing numbers. Discrete Mathematics, 2007, 307(15):1881-1897
[10] Xu J M. On bondage numbers of graphs:A survey with some comments. International Journal of Combinatorics, 2013:#595210
[11] Ma Q, Zhang S, Wang J. Bondage number of 1-planar graph. Applied Mathematics, 2010, 1:101-103
[12] Zhang X, Liu G. The structure of plane graphs with independent crossings and its applications to coloring problems. Central European Journal of Mathematics, 2013, 11(2):308-321
[13] Niu B, Zhang X. Linear arboricity of NIC-planar graphs. Acta Mathematicae Applicatae Sinica, English Series, 2019, 35(4):924-934
[14] Zhang X. Drawing complete multipartite graphs on the plane with restrictions on crossings. Acta Mathematica Sinica, English Series 2014, 30(12):2045-2053
[15] 徐俊明. 图论及其应用(第4版). 合肥:中国科学技术大学出版社, 2019
(Xu J M. Graph Theory with Applications (Fourth edition). Hefei:University of Science and Technology of China Press, 2019)
[16] Fabrici I, Madaras T. The structure of 1-planar graphs. Discrete Mathematics, 2007, 307(7-8):854-865
[17] Hartnell B L, Rall D F. A bound on the size of a graph with given order and bondage number. Discrete Mathematics, 1999, 197-198:409-413
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金面上基金资助项目(11871055),国家留学基金委公派留学(访问学者)项目(201906965003)和西安市科协青年人才托举计划资助项目(2018-6)资助
{{custom_fund}}