Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces

被引:0
作者
Vladimir Samodivkin
机构
[1] UACEG,
来源
Czechoslovak Mathematical Journal | 2013年 / 63卷
关键词
domination subdivision number; graph property; bondage number; Roman bondage number; induced-hereditary property; orientable genus; non-orientable genus; 05C69;
D O I
暂无
中图分类号
学科分类号
摘要
For a graph property P and a graph G, we define the domination subdivision number with respect to the property P to be the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to change the domination number with respect to the property P. In this paper we obtain upper bounds in terms of maximum degree and orientable/non-orientable genus for the domination subdivision number with respect to an induced-hereditary property, total domination subdivision number, bondage number with respect to an induced-hereditary property, and Roman bondage number of a graph on topological surfaces.
引用
收藏
页码:191 / 204
页数:13
相关论文
共 45 条
[1]  
Altshuler A.(1973)Construction and enumeration of regular maps on the torus Discrete Math 4 201-217
[2]  
Carlson K.(2006)On the bondage number of planar and directed graphs Discrete Math. 306 820-826
[3]  
Develin M.(2004)Domination subdivision numbers in graphs Util. Math. 66 195-209
[4]  
Favaron O.(2008)Connected domination subdivision numbers of graphs Util. Math. 77 101-111
[5]  
Haynes T. W.(2009)Paired-domination subdivision numbers of graphs Graphs Comb. 25 503-512
[6]  
Hedetniemi S. T.(2004)Hereditary domination and independence parameters Discuss. Math., Graph Theory. 24 239-248
[7]  
Favaron O.(2003)Total domination subdivision numbers J. Comb. Math. Comb. Comput. 44 115-128
[8]  
Karami H.(2004)Total domination subdivision numbers of graphs Discuss. Math., Graph Theory 24 457-467
[9]  
Sheikholeslami S.M.(1992)The weight of a graph. Combinatorics, Graphs and Complexity Proc. 4th Czech. Symp., Prachatice/Czech. 1990, Ann. Discrete Math. 51 113-116
[10]  
Favaron O.(2011)Roman bondage in graphs Discuss. Math., Graph Theory 31 753-761