Independent bondage number of a graph

被引:0
作者
Bruce Priddy
Haiying Wang
Bing Wei
机构
[1] University of Mississippi,Department of Mathematics
[2] China University of Geosciences (Beijing),School of Science
来源
Journal of Combinatorial Optimization | 2019年 / 37卷
关键词
Dominating set; Independent dominating set; Bondage number; Independent Bondage number;
D O I
暂无
中图分类号
学科分类号
摘要
A vertex set S of a simple finite graph G=(V;E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V;E)$$\end{document} is said to be an independent set if there is no edge between any pair of vertices of S and a dominating set if for any v∈V-S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v\in V-S$$\end{document}, uv∈E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$uv\in E$$\end{document} for some u∈S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u\in S$$\end{document}. If S is both independent and dominating in G, then S is an independent dominating set. Let i(G) denote the cardinality of a minimum independent dominating set of G. Set bi(G)=min{|E′|:E′⊆E,i(G)<i(G-E′)}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_i(G)=\min \{|E'|~: E'\subseteq E, i(G)<i(G-E')\}$$\end{document}, which we define as an independent bondage number of G. We initiate the study on properties of bi(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_i(G)$$\end{document} and present some upper and lower bounds on bi(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_i(G)$$\end{document} for some special classes of graphs. Further research problems will be proposed.
引用
收藏
页码:702 / 712
页数:10
相关论文
共 13 条
[1]  
Bauer D(1983)Domination alteration sets in graphs Discrete Math. 47 153-161
[2]  
Harray F(1990)The Bondage number of a graph Discrete Math. 86 47-57
[3]  
Nieminen J(1994)Bounds on the bondage number of a graph Discrete Math. 128 173-177
[4]  
Suffel C(2000)Bondage number of planar graphs Discrete Math. 222 191-198
[5]  
Fink JF(1995)A new bound for the bondage number of graphs with small domination number Australas. J. Comb. 12 27-35
[6]  
Jacobson MS(undefined)undefined undefined undefined undefined-undefined
[7]  
Kinch LF(undefined)undefined undefined undefined undefined-undefined
[8]  
Roberts J(undefined)undefined undefined undefined undefined-undefined
[9]  
Hartnell BJ(undefined)undefined undefined undefined undefined-undefined
[10]  
Rall DF(undefined)undefined undefined undefined undefined-undefined