Non-isolating Bondage in Graphs

被引:0
|
作者
Marcin Krzywkowski
机构
[1] University of Johannesburg,Department of Pure and Applied Mathematics
[2] Gdansk University of Technology,Faculty of Electronics, Telecommunications and Informatics
来源
Bulletin of the Malaysian Mathematical Sciences Society | 2016年 / 39卷
关键词
Domination; Bondage; Non-isolating bondage; Graph; Tree; 05C05; 05C69;
D O I
暂无
中图分类号
学科分类号
摘要
A dominating set of a 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 a set D of vertices of G such that every vertex of V(G)\D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V(G){\setminus }D$$\end{document} has a neighbor in D. The domination number of a graph G, denoted by γ(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma (G)$$\end{document}, is the minimum cardinality of a dominating set of G. The non-isolating bondage number of G, denoted by b′(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b'(G)$$\end{document}, is the minimum cardinality among all sets of edges E′⊆E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E' \subseteq E$$\end{document} such that δ(G-E′)≥1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta (G-E') \ge 1$$\end{document} and γ(G-E′)>γ(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma (G-E') > \gamma (G)$$\end{document}. If for every E′⊆E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E' \subseteq E$$\end{document} we have γ(G-E′)=γ(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma (G-E') = \gamma (G)$$\end{document} or δ(G-E′)=0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta (G-E') = 0$$\end{document}, then we define b′(G)=0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b'(G) = 0$$\end{document}, and we say that G is a γ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma $$\end{document}-non-isolatingly strongly stable graph. First we discuss various properties of non-isolating bondage in graphs. We find the non-isolating bondage numbers for several classes of graphs. Next we show that for every non-negative integer, there exists a tree having such non-isolating bondage number. Finally, we characterize all γ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma $$\end{document}-non-isolatingly strongly stable trees.
引用
收藏
页码:219 / 227
页数:8
相关论文
共 50 条
  • [41] On non-bipartite graphs with strong reciprocal eigenvalue property
    Barik, Sasmita
    Mishra, Rajiv
    Pati, Sukanta
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2024, 699 : 107 - 128
  • [42] Graphs of edge-intersecting and non-splitting paths
    Boyaci, Arman
    Ekim, Tinaz
    Shalom, Mordechai
    Zaks, Shmuel
    THEORETICAL COMPUTER SCIENCE, 2016, 629 : 40 - 50
  • [43] Facial Non-Repetitive Edge-Coloring of Plane Graphs
    Havet, Frederic
    Jendrol, Stanislav
    Sotak, Roman
    Skrabul'akova, Erika
    JOURNAL OF GRAPH THEORY, 2011, 66 (01) : 38 - 48
  • [44] Weak Vertex Cover Problem in Certain Non-Regular Graphs
    Angel, D.
    8TH INTERNATIONAL CONFERENCE ON ADVANCES IN COMPUTING & COMMUNICATIONS (ICACC-2018), 2018, 143 : 235 - 241
  • [45] On the structure of finite groups associated to regular non-centralizer graphs
    Alraqad, Tariq A.
    Saber, Hicham
    AIMS MATHEMATICS, 2023, 8 (12): : 30981 - 30991
  • [46] The undirected annihilating-ideal graphs over non-commutative rings
    Shen, Shouqiang
    Liu, Weijun
    RICERCHE DI MATEMATICA, 2024,
  • [47] Incremental Non-Dominated Sorting algorithms based on Irreducible Domination Graphs
    Mateo, P. M.
    Lahoz, D.
    Alberto, I.
    APPLIED SOFT COMPUTING, 2022, 128
  • [48] The largest non-integer real zero of chromatic polynomials of graphs with fixed order
    Dong, FM
    DISCRETE MATHEMATICS, 2004, 282 (1-3) : 103 - 112
  • [49] Graphs of Edge-Intersecting and Non-Splitting One Bend Paths in a Grid
    Boyaci, Arman
    Ekim, Tinaz
    Shalom, Mordechai
    Zaks, Shmuel
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2017, 19 (01)
  • [50] ON THE RAMSEY NUMBERS OF NON-STAR TREES VERSUS CONNECTED GRAPHS OF ORDER SIX
    Lortz, Roland
    Mengersen, Ingrid
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2023, 43 (02) : 331 - 349