66
Views
5
CrossRef citations to date
0
Altmetric
Section A

2-bondage in graphs

Pages 1358-1365 | Received 23 Mar 2012, Accepted 09 Nov 2012, Published online: 22 Feb 2013
 

Abstract

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) ∖ D has at least two neighbours in D. The 2-domination number of a graph G, denoted by γ2(G), is the minimum cardinality of a 2-dominating set of G. The 2-bondage number of G, denoted by b 2(G), is the minimum cardinality among all sets of edges E′ ⊆ E such that γ2(GE′)>γ2(G). If for every E′ ⊆ E we have γ2(GE′)=γ2(G), then we define b 2(G)=0, and we say that G is a γ2-strongly stable graph. First, we discuss the basic properties of 2-bondage in graphs. We find the 2-bondage numbers for several classes of graphs. Next we show that for every non-negative integer there exists a tree with such 2-bondage number. Finally, we characterize all trees with 2-bondage number equaling one or two.

2010 AMS Subject Classifications:

Acknowledgements

The research was supported by the Polish National Science Centre grant 2011/02/A/ST6/00201.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.