Non-isolating 2-bondage in graphs

A 2-dominating set of a graph G = (V,E) is a set D of vertices of G such that every vertex of V(G) \setminus D has at least two neighbors in D. The 2-domination number of a graph G, denoted by \gamma_2(G), is the minimum cardinality of a 2-dominating set of G. The non-isolating 2-bondage number of G...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the Mathematical Society of Japan 2013-01, Vol.65 (1), p.37-50
Main Author: KRZYWKOWSKI, Marcin
Format: Article
Language:English
Subjects:
05C05
05C69
2-domination
bondage
graph
non-isolating 2-bondage
tree
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A 2-dominating set of a graph G = (V,E) is a set D of vertices of G such that every vertex of V(G) \setminus D has at least two neighbors in D. The 2-domination number of a graph G, denoted by \gamma_2(G), is the minimum cardinality of a 2-dominating set of G. The non-isolating 2-bondage number of G, denoted by b_2'(G), is the minimum cardinality among all sets of edges E' \subseteq E such that \delta(G-E') \ge 1 and \gamma_2(G-E') > \gamma_2(G). If for every E' \subseteq E, either \gamma_2(G-E') = \gamma_2(G) or \delta(G-E') = 0, then we define b_2'(G) = 0, and we say that G is a \gamma_2-non-isolatingly strongly stable graph. First we discuss the basic properties of non-isolating 2-bondage in graphs. We find the non-isolating 2-bondage numbers for several classes of graphs. Next we show that for every non-negative integer there exists a tree having such non-isolating 2-bondage number. Finally, we characterize all \gamma_2-non-isolatingly strongly stable trees.
ISSN:0025-5645
1881-2333
DOI:10.2969/jmsj/06510037