与边控制相关的两类图
|
摘要
在图G中,如果存在一个边集D,使得不在D中的每一条边都与D中的某条边关联,则称D为G的边控制集.在G的所有边控制集中,包含边数最少的称为最小边控制集,其包含的边数称为边控制数,记为γ′(G).在一个图中,我们研究了加边或去边对该图边控制数的影响.一个图称为边控制临界图(边控制极小图)如果任意增加(去除)一条边都会使边控制数下降.在本文中,我们研究了这两类图的性质,并分别刻画了3-边控制临界图和3-点控制极小图.
An edge dominating set in a graph G is a set of edges D such that every edge not in D is adjacent to an edge of D. The edge domination number of G, denoted by γ′(G), is defined as the minimum cardinality of an edge dominating set of G. We consider the effects of edge removal or addition on the edge domination number of a graph. A graph G is edge domination critical graph(edge domination minimal graph, respectively) if the addition(removal, respectively) of any edge decreases γ′(G). In this paper we investigate various properties of these graphs. Moreover, we characterize 3-edge domination critical graphs and 3-edge domination minimal graphs.
An edge dominating set in a graph G is a set of edges D such that every edge not in D is adjacent to an edge of D. The edge domination number of G, denoted by γ′(G), is defined as the minimum cardinality of an edge dominating set of G. We consider the effects of edge removal or addition on the edge domination number of a graph. A graph G is edge domination critical graph(edge domination minimal graph, respectively) if the addition(removal, respectively) of any edge decreases γ′(G). In this paper we investigate various properties of these graphs. Moreover, we characterize 3-edge domination critical graphs and 3-edge domination minimal graphs.
引文
[1] West D B. Introduction to Graph Theory[M]. 2nd. Beijing:Pearson Education, 2004.
[2] Mitchell S, Hedetniemi S T. Edge domination in tree[J]. Congressus Numerantium, 1977, 19:489-509.
[3] Song W, Miao L, Wang H, et al. Maximal matching and edge domination in complete multipartite graphs[J]. International Journal of Computer Mathematics, 2014, 91:857-862.
[4] Xu B G. On edge domination numbers of graphs[J]. Discrete Mathematics, 2005, 294:311-316.
[5]庄蔚,杨卫华.外平面图的匹配控制数[J].新疆大学学报(自然科学版), 2016, 33(3):275-279.ZHUANG Wei, YANG Weihua.Paired domination number of outerplanar graphs[J].J Xinjiang Univ(Natural Sci Ed),2016,33(3):275-279.
[6]庄蔚.边控制临界图的性质[J].闽江学院学报, 2016, 157:1-4.ZHUANG Wei. The properties of edge domination critical graphs[J]. Journal of Minjiang University, 2016, 157:1-4.
[7]庄蔚.两种特殊图类直径的上界[J].厦门理工学院学报, 2015, 23:80-83.ZHUANG Wei. Upper bounds of the diameters of two classes of graphs[J]. Journal of Xiamen University of Technology,2015, 23:80-83.
[2] Mitchell S, Hedetniemi S T. Edge domination in tree[J]. Congressus Numerantium, 1977, 19:489-509.
[3] Song W, Miao L, Wang H, et al. Maximal matching and edge domination in complete multipartite graphs[J]. International Journal of Computer Mathematics, 2014, 91:857-862.
[4] Xu B G. On edge domination numbers of graphs[J]. Discrete Mathematics, 2005, 294:311-316.
[5]庄蔚,杨卫华.外平面图的匹配控制数[J].新疆大学学报(自然科学版), 2016, 33(3):275-279.ZHUANG Wei, YANG Weihua.Paired domination number of outerplanar graphs[J].J Xinjiang Univ(Natural Sci Ed),2016,33(3):275-279.
[6]庄蔚.边控制临界图的性质[J].闽江学院学报, 2016, 157:1-4.ZHUANG Wei. The properties of edge domination critical graphs[J]. Journal of Minjiang University, 2016, 157:1-4.
[7]庄蔚.两种特殊图类直径的上界[J].厦门理工学院学报, 2015, 23:80-83.ZHUANG Wei. Upper bounds of the diameters of two classes of graphs[J]. Journal of Xiamen University of Technology,2015, 23:80-83.