Graph theory has become one of the most powerful mathematical tools in the analysis and study of the architecture of networks whose vertices represent the components of the system and the edges represent connection between a pair of vertices that enable mutual communication. The vulnerability of a communication network measures the resistance of network to the disruption of operation after the failure of certain stations or communication links. For any communica-tion network greater degrees of stability or less vulnerability is required. Vulnerability can be measured by certain parameters like domination, bondage number, connectivity, betweenness, binding number, toughness, scattering number, integrity etc. Graph theory is among the popular methods for solving many complex problems. Graph theory increases its development and us-age area due to the easy modelling of daily problems and successful results of effective solution methods. The dominant nodes indicate the dominance of the people or objects modelled on the graph over each other. However, minimum domination set aims to connect all vertices in the graph with the least number of vertices selected on the graph. Determining the minimum dom-inating set in graphs is one of the most diffucult problems defined as NP-hard. When the usage areas of dominating sets in graphs examined, it is seen to provide significant gains in many ar-eas such as social networks, transportation systmes, telecommunication, defence industry, health systems, etc.

In a graph G = (V (G), E(G)), a subset S ⊆ V (G) of vertices is a dominating set if ev-ery vertex in V (G) − S is adjacent to at least one vertex of S. The domination number γ(G) is the minimal cardinality of a dominating set. One of the vulnerability parameters based on domination number known as bondage number in a graph G examines the situation in which the domination number increases if some connections are broken. The opposite parameter, that is, examining the decrease in the domination number, is the reinforcement number. The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than γ(G). That is,

b(G) = min{|S| : S ⊆ E(G), γ(G − S) > γ(G)}.

We call such an edge set S that γ(G − S) > γ(G) the bondage set and the minimum one the minimum bondage set. If b(G) does not exist, for example empty graphs, then b(G) = ∞ is defined.

The bondage number was introduced by Bauer, Harary, Nieminen and Suffel [3] , and has been further studied by Fink, Jacobson, Kinch and Roberts[8], Hartnell and Rall[4] and others. Later, the bondage number for middle graphs and complementary prism graphs was studied in [1, 2].

In this paper, the graph G is taken as a simple, finite and undirected graph with vertex set V (G) and edge set E(G). The distance d(u, v) between two vertices u and v in G is the length of a shortest path joining them if any; otherwise d(u, v) = ∞. A shortest u−v path is often called a geodesic. The diameter of G, denoted by diam(G) is the largest distance between two vertices in V (G). The number of the neighbor vertices of the vertex v is called degree of v and denoted by degG(v). The minimum and maximum degrees of a vertex of G are denoted by δ(G) and ∆(G). A vertex v is said to be pendant vertex if degG(v) = 1. A vertex u is called support if u is adjacent to a pendant vertex [5]. Let u be a vertex of a graph G = (V, E). Then N(u) = {v ∈ V (G), v and u are adjacent} is the open neighborhood of u, and N[u] = {u} ∪ N(u) denotes the closed neighborhood of u. The eccentricity e(v) of a vertex v in a connected graph G is max d(u, v) for all u in G. The radius r(G) is the minimum eccentricity of the vertices. Note that the maximum eccentricity is the diameter. A vertex v is a central vertex if e(v) = r(G), and the center of G is the set of all central vertices [5]. The connectivity κ = κ(G) of a graph G is the minimum number of vertices whose removal results in a disconnected or trivial graph. A vertex and an edge are said to cover each other if they are incident. A set of vertices which covers all the edges of a graph G is called a vertex cover for G, while a set of edges which covers all the vertices is a edge cover. The smallest number of vertices in any vertex cover for G is called its vertex covering number and is denoted by α0(G) or α0. Similarly, α1(G) or α1 is the smallest number of edges in any edge cover of G and is called its edge covering number. A set of vertices in G is independent if no two of them are adjacent. The largest number of vertices in such a set is called the vertex independence number of G and is denoted by β0(G) or β0. Analogously, an independent set of edges of G has no two of its edges adjacent and the maximum cardinality of such a set is the edge independence number β1(G) or β1[5]. The complement G of a simple graph G is the simple graph with vertex set V (G) defined by uv ∈ E(G) if and only if uv / ∈ E(G). The corona (G1 ◦ G2) of two graphs G1 and G2 is defined as the graph G obtained by taking one copy of G1 (which has p1 vertices) and p1 copies of G2, and then joining the ith vertex of G1 to every vertex in the ith copy of G2[11]. Let G1 and G2 be two graphs with vertex sets are V (G1) and V (G2); edge sets are E(G1) and E(G2) respectively. Then, the join of G1 + G2 of two graphs G1 and G2 is the graph with vertex set V (G1 + G2) = V (G1) ∪ V (G2) and edge set E(G1 + G2) = E(G1) ∪ E(G2) ∪ {uv : u ∈ V (G1), v ∈ V (G2)}[13].

The line graph L(G) of G has the edges of G as its vertices which are adjacent in L(G) if and only if the corresponding edges are adjacent in G. We call the complement of line graph L(G) as the jump graph J(G) of G. The jump graph J(G) of a graph G is the graph defined on E(G) and in which two vertices are adjacent if and only if they are not adjacent in G. Since both L(G) and J(G) are defined on the edge set of a graph G, it follows that isolated vertices of G (if G has) play no role in line graph and jump graph transformation. We assume that the graph G under consideration is nonempty and has no isolated vertices [6, 14]. Aim of the paper is to establish the bondage number for jump graph of some certain trees. Graph operations like join, corona, line and jump are play important role in obtaining larger structures from small structures. Moreover, trees are more consistent than general graph structures since each edge is an intersection edge. Undirected trees are the simplest yet most important class of graphs for computing domination and bondage numbers. Therefore, the study of bondage number for jump graphs of trees may be useful in studying other graph families.

In this section, some well-known basic results are given with regard to domination and bondage number.

Theorem 2.1. [8] For a complete graph Kn of order n ≥ 2, then b(Kn) = ⌈ ⌉.

Theorem 2.2. [8] For a path graph Pn of order n ≥ 2, then

2, if n ≡ 1(mod3) b(Pn) = 1, otherwise Theorem 2.3. [8] For a cycle graph Cn of order n ≥ 3, then

3, if n ≡ 1(mod3) b(Cn) = 2, otherwise

Theorem 2.4. [8] For a star graph K1,n of order n + 1, where n ≥ 2. Then, b(K1,n) = 1.

Theorem 2.5. [8] If G is a nonempty graph with a unique minimum dominating set, then b(G) =

Theorem 2.6. [8] If T is a nontrivial tree, then b(T) ≤ 2.

Theorem 2.7. [8] If G is a connected graph of order n ≥ 2, then b(G) ≤ n − 1.

Theorem 2.8. [8] If G is a nonempty graph, then

b(G) ≤ min{deg(u) + deg(v) − 1 : u and v are adjacent vertices.}

Theorem 2.9. [8] If ∆(G) and δ(G) denote respectively the maximum and minimum degree among all vertices of nonempty connected graph G, then b(G) ≤ ∆(G)+ δ(G) − 1.

Theorem 2.10. [8] If G is a nonempty graph with domination number γ(G) ≥ 2, then b(G) ≤ (γ(G) − 1)∆(G) + 1.

Theorem 2.11. [8] If G is a connected graph of order n ≥ 2, then b(G) ≤ n − γ(G) + 1.

Theorem 2.12. [8] If G is a nonempty graph , then b(G) ≤ ∆(G) + 1.

Theorem 2.13. [4] If G has edge connectivity κ, then b(G) ≤ ∆(G) + κ − 1.

Theorem 2.14. [2] If G is a nonempty connected graph of order n with α0(G) = 1, then b(G) =

Theorem 2.15. [14] Let G(p, q) be a graph with p = |V | and q = |E|, then a) For any connected (p, q) graph G, γ(J(G)) ≤ q − β1(G) + 1.

p+1 2

b) For any connected (p, q) graph G, γ(G) + γ(J(G)) < ( ) .

c) For any connected graph G with diameter, diam(G) ≥ 2, γ(J(G)) ≥ 2.

d) For any tree T with diameter greater than 3, γ(J(T)) = 2.

e) For any connected (p, q) graph G, γ(J(G)) ≥ q − ∆(G) f) For any connected (p, q) graph G, 2 ≤ γ(J(G)) ≤ ⌊ ⌋.

g) For any connected graph G without pendant vertex, γ(J(G)) ≤ δ(G).

In this section, we calculated the bondage number for jump graph of some trees as comet graph Cn,t, k − ary Hn, caterpillar Tn,m, the graph En and banana tree Bn,k.

Definition 3.1. [9] For integer n ≥ 2 and t ≥ 1, the comet graph Cn,t is defined to be the graph of order n + t + 1 obtained from disjoint union of a star K1,n and a path Pt with t vertices by adding an edge joining the central vertex of the star with an end-vertex of the path. A Comet graph C5,3 is illustrated in Figure 1.

Theorem 3.2. The bondage number for the jump graph of comet graph Cn,t is b(J(Cn,t)) = t−2.

Proof. We know from the Theorem 2.15(d) that γ(J(Cn,t)) = 2. We can label the corresponding vertices to the relevant edges in the comet graph Cn,t as V (J(Cn,t)) = {c1, c2, ..., cn, cn+1, (n+1)(n+2), (n+2)(n+3), ..., (t−2)(t−1), (t−1)t}. There are n vertices c1, c2, ..., cn degree of t−1, one vertex cn+1 degree of t−2, t−2 vertices (n+1)(n+2), (n+2)(n+3), ..., (t−2)(t−1) degree of n + t − 3 and one vertex (t − 1)t degree of n + t − 2 in J(Cn,t). If we delete the edges that are incident to the vertex cn+1 with minimum degree, then the graph formed by join of the complement graph Pt−1 and n disjoint vertices means the complement graph Kn and one isolated vertex cn+1 remain. If we denote the set of the deleted edges by S, then γ(J(Cn,t) − S) = γ(Kn + Pt−1) = 2, except the vertex cn+1. Since, cn+1 dominates itself, the domination number of the remaining graph results with 3, which is one more than γ(J(Cn,t)). Hence, we have b(J(Cn,t)) = t − 2 because of deg(cn+1) = t − 2. This completes the proof.

Definition 3.3. [10] The complete k − ary tree Hn of depth n is the rooted tree in which all vertices at level n − 1 or less have exactly k children, and all vertices at level n are leaves. A complete 2 − ary tree H is illustrated in Figure 2.

Theorem 3.4. The bondage number for the jump graph of k − ary tree Hn is b(J(Hn)) =

k −k k +k−2

( ).

k−1 k−1

Proof. The Line graph of Hn is the graph formed by combining the root vertices of two graphs

k k k

H . The jump graph J(Hn), which is the complement of line graph L(Hn) is a graph whose root vertex of one of H is adjacent to all vertices except the root vertex of the other graph H . All other vertices of these two components are adjacent to each other. That is, the root

k 2 3 n−1

vertex of H is adjacent to the all remaining vertices A = k + k + k + ... + k =

k −k k k −1

of H ; are adjacent to A + 1 = vertices including the root vertex of the other

k−1 n−1 k−1

component H . We know γ(J(H )) = 2 from the Theorem 2.15(d). Let S be the set of

n−1 n−1

edges connecting these two components. So, if we disconnect these two compenents, which are

k k k

the same, then γ(J(Hn)−S) = 2γ(J(H )) = 2+2 = 4 > 2 = γ(J(Hn). In order to achieve this, edges equal to the cardinality of the edge set S must be removed from the J(Hn). Hence,

n n n n

k 2 k −k 2 k −k k −k k +k−2

b(J(Hn)) = A + 2A = ( ) + 2 = ( ) is obtained and this completes the

k−1 k−1 k−1 k−1

proof.

Definition 3.5. [7] A tree T is called a caterpillar, if removal of all its pendant vertices results in a path called the spine of T, denoted by sp(T). If all vertices of sp(T) have equal number of pendant vertices, then the resulting graph is called a regular caterpillar. A regular caterpillar can also be defined as the corona of two special graph types. That is, if Tn,m is a regular caterpillar of order nm + n, then T = ∼ P ◦ mK . A regular caterpillar T is illustrated in Figure 3.

n,m n 1 5,3 Theorem 3.6. The bondage number for the jump graph of regular caterpillar graph Tn,m is b(J(Tn,m)) = nm + n − 2m − 4.

Proof. Spines of line graph and its complement jump graph of regular caterpillar Tn,m contains n − 1 vertices. The vertex which has maksimum degree in L(Tn,m) is the vertex with mini-mum degree in J(Tn,m). If we delete the edges that are incident to the vertex with minimum degree in J(Tn,m), then two graphs J(Tt,m) and J(Tn−t,m) remain. We know γ(J(Tt,m)) = γ(J(Tn−t,m)) = 2. As the isolated vertex denoted by v dominates itself, the domination number of the remaining graph results with 5, which is 3 more than γ(J(Tn,m)). Since, deg(v) = 2t + 2 in L(Tn,m) and deg(v) = nm + n − 2m − 4 in J(Tn,m), b(J(Tn,m)) = nm + n − 2m − 4 is obtained. This completes the proof.

Definition 3.7. [12] The graph En is a tree which has t legs and each leg has n vertices. Thus, En has nt + 2 vertices. The graph E is illustrated in Figure 4.

Theorem 3.8. The bondage number for the jump graph of En is b(J(En)) = (n − 1)t.

Proof. L(En) is the graph formed by combining the one of the pendant vertices of each path graph Pn with the vertex uv. Hence, there are the vertex uv degree of t, (n − 1)t vertices degree of 2 and t pendant vertices in L(En). The vertex with the minimum degree is the vertex uv in J(En) and deg(uv) = (n − 1)t. By definition, the γ-set includes the vertices of maximum degree. In order to increase the cardinality of the γ-set, the edge set S, which consists the edges that are incident to the vertex uv must be remove from J(En). Therefore, γ(J(En) − uv) = 2 and uv must dominate itself. Hence, γ(J(En) − S) = 3, which is 1 more than γ(J(En). This completes the proof.

Definition 3.9. [15] Banana tree is obtained by linking one leaf of each of n copies of an k vertices star graph structure with a single root vertex that is distinct from all the stars and the tree is denoted by Bn,k. The Banana tree B3,5 is illustrated in Figure 5.

Theorem 3.10. The bondage number for the jump graph of banana tree Bn,k is

nt − t, if n < t b(J(Bn,k)) = nt − n − 1, if n ≥ t

Proof. As in the previous proof, when the minimum degree vertex in J(Bn,k) is isolated, the bondage number of the remaining graph is 2. Let’s denote the vertex with the minimum degree by v. If n < t, then deg(v) = nt − t and if n ≥ t, then deg(v) = nt − n − 1. Hence, we have

nt − t, if n < t b(J(Bn,k)) = nt − n − 1, if n ≥ t

This completes the proof.

In this paper, we studied the bondage number for jump graphs of some trees including Comet graph Cn,t, k − ary tree Hn, caterpillar graph Tn.m, the graph En and banana tree Bn,k. Gen-eral results were obtained for these structures. In the graphs examined, it was observed that the bondage number was obtained by splitting the graph into two components or by leaving an iso-lated vertex. As one of the most relevant application areas, a problem related to social networks was presented. Thus, the increase in the robustness and stability of the given graphs by breaking some links was investigated.

The author expresses her sincere gratitude to the area editor and reviewer for useful advice.