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 条
  • [31] Generalized indices of non-primitive graphs
    Bo, Z
    INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, 2003, 34 (01) : 163 - 172
  • [32] Matchings in graphs on non-orientable surfaces
    Tesler, G
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 78 (02) : 198 - 231
  • [33] Generalized exponents of non-primitive graphs
    Shao, JY
    Hwang, SG
    LINEAR ALGEBRA AND ITS APPLICATIONS, 1998, 279 (1-3) : 207 - 225
  • [34] Intersection Graphs of Non-crossing Paths
    Chaplick, Steven
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2019), 2019, 11789 : 311 - 324
  • [35] Using trees to build non-singular bond graphs from electric circuit graphs
    Buisson, J
    Cormerais, H
    Richard, PY
    JOURNAL OF THE FRANKLIN INSTITUTE-ENGINEERING AND APPLIED MATHEMATICS, 2000, 337 (05): : 543 - 554
  • [36] A comparison of some conditions for non-hamiltonicity of graphs
    Hoede, C
    ARS COMBINATORIA, 1999, 51 : 149 - 159
  • [37] A NOTE ON NON-DOMINATING SET PARTITIONS IN GRAPHS
    Desormeaux, Wyatt J.
    Haynes, Teresa W.
    Henning, Michael A.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (04) : 1043 - 1050
  • [38] Non-backtracking random walks and cogrowth of graphs
    Ortner, Ronald
    Woess, Wolfgang
    CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 2007, 59 (04): : 828 - 844
  • [39] Non-planar extensions of subdivisions of planar graphs
    Norin, Sergey
    Thomas, Robin
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 121 : 326 - 366
  • [40] Large Cayley Graphs and Vertex-Transitive Non-Cayley Graphs of Given Degree and Diameter
    Macbeth, Heather
    Siagiova, Jana
    Siran, Jozef
    Vetrik, Tomas
    JOURNAL OF GRAPH THEORY, 2010, 64 (02) : 87 - 98