三类超越可平面图的结构及其约束数

The Structure and the Bondage Number of Three Classes of Beyond-planar Graphs

如果一个图可以嵌入在平面内使得每条边最多被交叉一次,则称该图为1-可平面图.如果一个图可以嵌入在平面内使得任何两个交叉不共享关联点,则称该图为IC-可平面图.如果一个图可以嵌入在平面内使得任何两个交叉最多共享一个关联点,则称该图为NIC-可平面图.1-可平面图,IC-可平面图与NIC-可平面图是三类重要的超越可平面图,它们在模块网络,社交网络和生物网络上有着重要的应用.图的约束数是为了使图的支配数严格增加所需要删除的最少的边数,它是衡量网络脆弱性的一个重要参数.本文考虑1-可平面图,IC-可平面图与NIC-可平面图的结构,并利用得到的结构定理证明了它们的约束数分别最多是13,11与12.

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.