DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 16(2) (1996) 111-117
DOI: 10.7151/dmgt.1026

THE COBONDAGE NUMBER OF A GRAPH

V.R. Kulli and B. Janakiram

Department of Mathematics, Gulbarga University
Gulbarga-585 106, India

Abstract

A set D of vertices in a graph G = (V,E) is a dominating set of G if every vertex in V-D is adjacent to some vertex in D. The domination number γ(G) of G is the minimum cardinality of a dominating set. We define the cobondage number bc(G) of G to be the minimum cardinality among the sets of edges X ⊆ P2(V)-E, where P2(V) = {X ⊆ V:|X| = 2} such that γ(G+X)< γ(G). In this paper, the exact values of bc(G) for some standard graphs are found and some bounds are obtained. Also, a Nordhaus-Gaddum type result is established.

Keywords: graph, domination number, cobondage number.

1991 Mathematics Subject Classification: 05C.

References

[1] E.J. Cockayne and S.T. Hedetniemi, Domination of undirected graphs - A survey, In: Theory and Applications of Graphs (Lecture Notes in Math. 642, Spring-Verlag, 1978) 141-147.
[2] J.F. Fink, M.S. Jakobson, L.F. Kinch and J. Roberts, The bondage number of a graph, Discrete Math. 86 (1990) 47-57, doi: 10.1016/0012-365X(90)90348-L.
[3] F. Harary, Graph Theory (Addison-Wesley, Reading Mass., 1969).
[4] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175-177, doi: 10.2307/2306658.