Electronic Journal of Graph Theory and Applications

Vladimir Samodivkin

Departments of Mathematics University of Architecture, Civil Engineering and Geodesy Sofia, Bulgaria

vl.samodivkin@gmail.com

The bondage number b(G) of a graph G is the smallest number of edges whose removal from G results in a graph with larger domination number. We obtain sufficient conditions for the validity of the inequality \(b(G) \leq 2s - 2\), provided G has degree s vertices. We also present upper bounds for the bondage number of graphs in terms of the girth, domination number and Euler characteristic. As a corollary we give a stronger bound than the known constant upper bounds for the bondage number of graphs having domination number at least four. Several unanswered questions are posed.

Keywords: bondage number, domination number, Euler's formula, girth, average degree

Mathematics Subject Classification: 05C69

DOI: 10.5614/ejgta.2018.6.1.1

1. Introduction

An orientable compact 2-manifold \(\mathbb{S}_h\) or orientable surface \(\mathbb{S}_h\) (see [21]) of genus h is obtained from the sphere by adding h handles. Correspondingly, a non-orientable compact 2-manifold \(\mathbb{N}_q\) or non-orientable surface \(\mathbb{N}_q\) of genus q is obtained from the sphere by adding q crosscaps. Compact 2-manifolds are called simply surfaces throughout the paper. The Euler characteristic is defined by \(\chi(\mathbb{S}_h) = 2 - 2h\), \(h \geq 0\), and \(\chi(\mathbb{N}_q) = 2 - q\), \(q \geq 1\). The Euclidean plane \(\mathbb{S}_0\), the projective plane \(\mathbb{N}_1\), the torus \(\mathbb{S}_1\), and the Klein bottle \(\mathbb{N}_2\) are all the surfaces of non-negative Euler characteristic.

Received: 4 February 2015, Revised: 26 November 2017, Accepted: 13 December 2017.

We shall consider graphs without loops and multiple edges. A graph G is embeddable on a topological surface \(\mathbb M\) if it admits a drawing on the surface with no crossing edges. Such a drawing of G on the surface \(\mathbb M\) is called an embedding of G on \(\mathbb M\). If a graph G is embedded in a surface \(\mathbb M\) then the connected components of \(\mathbb M-G\) are called the faces of G. For such a graph G, we denote its vertex set, edge set, face set, maximum degree, and minimum degree by V(G), E(G), F(G), \(\Delta(G)\), and \(\delta(G)\), respectively. Set |G|=|V(G)|, ||G||=|E(G)|, and f(G)=|F(G)|. An embedding of a graph G on a surface \(\mathbb M\) is said to be 2-cell if every face of the embedding is homeomorphic to an open disc. The Euler's inequality states

\[|G| - ||G|| + f(G) \ge \chi(\mathbb{M}) \tag{1}\]

for any graph G that is embedded in \(\mathbb{M}\). Equality holds if G is 2-cell embedded in \(\mathbb{M}\). By the genus h (the non-orientable genus q) of a graph G we mean the smallest integer h (q) such that G has an embedding into \(\mathbb{S}_h\) (\(\mathbb{N}_q\), respectively).

The girth of a graph G, denoted as g(G), is the length of a shortest cycle in G; if G is a forest then \(g(G) = \infty\). For any vertex x of a graph G, \(N_G(x)\) denotes the set of all neighbors of x in G, \(N_G[x] = N_G(x) \cup \{x\}\) and the degree of x is \(d_G(x) = |N_G(x)|\). For a subset \(A \subseteq V(G)\), let \(N_G(A) = \bigcup_{x \in A} N_G(x)\), \(N_G[A] = N_G(A) \cup A\), and \(\langle A, G \rangle\) be the subgraph of G induced by G. The distance between two vertices G, G is denoted by G. The average degree G is defined as G is defined as G.

An independent set is a set of vertices in a graph, no two of which are adjacent. The independence number \(\beta_0(G)\) of a graph G is the size of the largest independent set in G. A dominating set for a graph G is a subset \(D \subseteq V(G)\) of vertices such that every vertex not in D is adjacent to at least one vertex in D. The minimum cardinality of a dominating set is called the domination number of G and is denoted by \(\gamma(G)\). The concept of domination in graphs has many applications in a wide range of areas within the natural and social sciences. One measure of the stability of the domination number of G under edge removal is the bondage number b(G) defined in [2] (previously called the domination line-stability in [2]) as the smallest number of edges whose removal from G results in a graph with larger domination number. We refer the reader to [31] for a detailed survey on this topic. In general it is NP-hard to determine the bondage number (see Hu and Xu [11]), and thus useful to find bounds for it.

The main outstanding conjecture on the bondage number is the following:

Conjecture 1 (Teschner [29]). For any graph G, \(b(G) \leq \frac{3}{2}\Delta(G)\).

Hartnell and Rall [8] and Teschner [30] showed that for the Cartesian product \(G_n = K_n \times K_n\), \(n \ge 2\), the bound of Conjecture 1 is sharp, i.e. \(b(G_n) = \frac{3}{2}\Delta(G_n)\). Teschner [29] also proved that Conjecture 1 holds when the domination number of G is not more than 3.

The study of the bondage number of graphs, which are 2-cell embeddable on a surface having negative Euler characteristic was initiated by Gagarin and Zverovich [6] and is continued by the same authors in [7], Jia Huang in [12] and the present author in [24]. All these authors obtain upper bounds for the bondage number in terms of maximum degree and/or orientable and non-orientable genus of a graph. In [25], the present author gives upper bounds for the bondage number in terms of order, girth and Euler characteristic of a graph. By Theorem 10 (ii) [7] or by Theorem B(ii)

below, it immediately follows that Conjecture 1 is true for any graph G such that all the following is valid: (a) G is 2-cell embeddable in a surface \(\mathbb M\) with \(\chi(\mathbb M)<0\), (b) \(|G|>-12\chi(\mathbb M)\), and (c) \(\Delta(G)\geq 8\).

In this paper we concentrate mainly on the case when a graph G is 2-cell embeddable in a surface \(\mathbb M\) and \(|G| \leq -12\chi(\mathbb M)\). The rest of the paper is organized as follows. Section 2 contains preliminary results. In section 3 we give new arguments that improve the known upper bounds on the bondage number at least when \(-7\chi(\mathbb M)/(\delta(G)-5) < |G| \leq -12\chi(\mathbb M), \ \delta(G) \geq 6\). We propose a new type of upper bound on the bondage number of a graph. Namely we obtain sufficient conditions for the validity of the inequality \(b(G) \leq 2s-2\), where G is a graph having degree s vertices, \(s \geq 5\). In particular, we prove that if a connected graph G is 2-cell embeddable in an orientable/non-orientable surface \(\mathbb M\) with negative Euler characteristic then \(b(G) \leq 2\delta-2\) whenever \(-14\chi(\mathbb M) < \delta(G) - 4 + 2(\delta(G) - 5)|G|\) and \(\delta(G) \geq 6\). We also improve the known upper bounds for b(G) when a graph G is embeddable on at least one of \(\mathbb N_1, \mathbb N_2, \mathbb N_3, \mathbb N_4\) and \(\mathbb S_2\). In section 4 we give tight lower bounds for the number of vertices of graphs in terms of Euler characteristic and the domination number. We also present upper bounds for the bondage number of graphs in terms of the girth, domination number and Euler characteristic. As a corollary, in section 5 we give a stronger bound than the known constant upper bounds for the bondage number of graphs having domination number at least 4.

2. Known and preliminary results

In this section we recall several known upper bounds on the bondage number of a graph and prove some useful lemmas. We need the following notations and definitions.

• \(V_{\leq r}(G) = \{x \in V(G) \mid d_G(x) \leq r\}, r \geq 1,\)
• \(V_r(G) = \{x \in V(G) \mid d_G(x) = r\}, r \ge 1,\)
• \(b_1(G) = \min\{d_G(x) + d_G(y) 1 \mid x, y \in V(G) \text{ and } 1 \le d_G(x, y) \le 2\},\\)
• \(b_2(G) = \min_{x,y \in V(G)} \{ d_G(x) + d_G(y) 1 |N_G(x) \cap N_G(y)| \mid xy \in E(G) \},\)
• \(b_3(G) = \min_{x,y \in V(G)} \{ \max \{ d_G(x) + d_G(y) 1 |N_G(x) \cap N_G(y)|, d_G(x) + d_G(y) 3 \} \mid xy \in E(G) \},\)
• [13] \(B(G) = \min\{b_1(G), b_2(G)\},\\)
• \(B'(G) = \min\{b_1(G), b_3(G)\}.\)

Theorem A. If G is a nontrivial graph, then

• (i) (Hartnell and Rall [9]) \(b(G) \le b_1(G) \le 2ad(G) 1\);
• (ii) (Hartnell and Rall [8]) \(b(G) \leq b_2(G)\).

By Theorem A and the above definitions we have \(b_2(G) \leq b_3(G)\) and

\[b(G) \le B(G) \le B'(G) \le b_1(G) \le 2ad(G) - 1.\] (2)

Note that, if a graph G has no triangles then \(B(G) = B'(G) = b_1(G)\).

Theorem B. (Samodivkin [25]). Let G be a connected graph embeddable on a surface \(\mathbb{M}\) whose Euler characteristic \(\chi\) is as large as possible and let g(G) = g. If \(\chi \leq -1\) then:

(i) \[ad(G) \le \frac{2g}{g-2}(1 - \frac{\chi}{|G|});\]

(ii) \[b(G) \le 2ad(G) - 1 \le 3 + \frac{8}{g-2} - \frac{4\chi g}{|G|(g-2)}\].

The same upper bound for b(G), in case when \(g \in \{3, 4\}\), is obtained by Gagarin and Zverovich [6].

Theorem C. (Gagarin and Zverovich [7]). Let G be a connected graph 2-cell embedded in a surface \(\mathbb{M}\) with \(\chi(\mathbb{M}) = \chi \leq -1\). Then

\[b(G) \le 2ad(G) - 1 \le 11 + \frac{3\chi(\sqrt{17 - 8\chi} - 3)}{\chi - 1}.\]

Theorem D. (Samodivkin [24]). Let G be a connected toroidal or Klein bottle graph. Then \(b_2(G) \leq \Delta(G) + 3\) with equality if and only if one of the following conditions is valid:

• (P3) G is 4-regular without triangles:
• (P4) G is 6-regular and no edge of G belongs to at least 3 triangles.

In [5], Frucht and Harary define the corona of two graphs \(G_1\) and \(G_2\) to be the graph \(G = G_1 \circ G_2\) formed from one copy of \(G_1\) and \(|G_1|\) copies of \(G_2\), where the ith vertex of \(G_1\) is adjacent to every vertex in the ith copy of \(G_2\).

Theorem E. (Carlson and Develin [3]). Let G be a graph of the form \(G = H \circ K_1\). Then \(b(G) = \delta(H) + 1\).

Lemma F. (Sachs [23], pp. 226-227). Let G be a connected graph embeddable in a surface \(\mathbb{M}\). If \(\mathbb{M} \in \{\mathbb{S}_0, \mathbb{N}_1\}\) then \(\delta(G) \leq 5\). If \(\chi(\mathbb{M}) \leq 1\) then \(\delta(G) \leq \left| (5 + \sqrt{49 - 24\chi(\mathbb{M})})/2 \right|\).

Lemma 2.1. Let G be a graph embedded in a surface \(\mathbb{M}\). If \(g(G) = g < \infty\) then \(||G|| \le (|G| - \chi(\mathbb{M})) \frac{g}{g-2}\).

Proof. Case 1: The graph G is connected. Then there is a surface \(\mathbb{M}_1\) on which G can be 2-cell embedded. Since clearly \(gf(G) \leq 2\|G\|\), by (1) we have \(\chi(\mathbb{M}) \leq \chi(\mathbb{M}_1) = |G| - \|G\| + f(G) \leq |G| - \|G\| + \frac{2}{q}\|G\|\), and the result easily follows.

Case 2: The graph G is disconnected. Then there is a connected supergraph \(G_1\) for G such that (a) \(V(G_1) = V(G)\) and \(E(G) \subsetneq E(G_1)\), and (b) \(G_1\) can be embedded in \(\mathbb{M}\). By Case 1 we immediately have \(||G|| < ||G_1|| \le (|G_1| - \chi(\mathbb{M})) \frac{g}{g-2}\).

The next lemma is fairly obvious and hence we omit the proof.

Lemma 2.2 (J. van den Heuvel [14]). Let G be a connected graph 2-cell embedded in a surface \(\mathbb{M} \in \{\mathbb{S}_h, \mathbb{N}_q\}\), \(v \in V(G)\) and \(d_G(v) \geq 2\). Let \(E_v = \{xy \mid x, y \in N_G(v), x \neq y, xy \notin E(G)\}\). Then there is a subset \(D \subseteq E_v\), such that the graph H = G + D is still 2-cell embedded in \(\mathbb{M}\) and

(i) \(\langle N_H(v), H \rangle\) is connected;

(ii) \(\langle N_H(v), H \rangle\) is Hamiltonian when \(d_G(v) \geq 3\).

Lemma 2.3. Let G be a connected graph 2-cell embedded in a surface \(\mathbb{U}\). Let \(s \geq 3\), \(V_{\leq s} - V_{\leq 2} \neq \emptyset\) and \(B'(G) \geq 2s-1\). Let \(I = \{x_1, x_2, \ldots, x_k\}\) be an independent dominating set in \(\langle V_{\leq s}, G \rangle\). Then \(V_{\leq s-1} \subseteq I\) and there is a supergraph \(G_k\) for G which is 2-cell embedded in \(\mathbb{U}\) such that \(V(G_k) = V(G)\), \(E(G) \subseteq E(G_k)\) and the following hold:

• (a) I is an independent set of \(G_k\);
• (b) if \(u \in (V(G) N_G(I)) \cup N_G(V_1)\) then \(N_{G_k}(u) = N_G(u)\);
• (c) if \(u \in I\), \(v \in V_{\leq s-1}(G)\) and \(u \neq v\) then \(d_{G_k}(u, v) = d_G(u, v) \geq 3\);
• (d) if \(u \in I\), \(d_G(u) = r \ge 3\) and \(v \in N_G(u)\) then \(d_{G_k}(v) \ge 2s r + 2\);
• (e) if \(u \in I\), \(d_G(u) = 2\) and \(v \in N_G(u)\) then \(d_{G_k}(v) \ge 2s 1\).

Proof. Since \(B'(G) \ge 2s - 1\), the following claim is valid.

Claim 1. If \(x \in V_r(G)\), \(r \leq s\), \(y \in V(G)\) and \(1 \leq d_G(x,y) \leq 2\), then \(d_G(y) \geq 2s - r\).

Hence \(V_{\leq s-1}\subseteq I\) and \(d_G(x,y)\geq 3\) whenever \(x\neq y, x\in V_{\leq s}\) and \(y\in V_{\leq s-1}\). Since G is 2-cell embedded, using Lemma 2.2 consecutively k times we obtain the graphs \(G_0=G,G_1,\ldots,G_k\), as follows. For \(r=1,2,\ldots,k\) let \(G_r=G_{r-1}+F_r\), where \(F_r\subseteq \{xy\mid x,y\in N_G(x_r),x\neq y,xy\not\in E(G_{r-1})\}\), such that \(G_r\) is still a 2-cell embedded in \(\mathbb U\) and (i) if \(d_G(x_r)\geq 3\) then \(\langle N_{G_r}(x_r),G_r\rangle\) is Hamiltonian, and (ii) if \(d_G(x_r)=2\) then \(x_r\) belong to a triangle of \(G_r\). Clearly, if \(d_G(x_r)\geq 3\) then \(\langle N_{G_k}(x_r),G_k\rangle\) is Hamiltonian and if \(d_G(x_r)=2\) then \(x_r\) belongs to a triangle of \(G_k\), \(r=1,2,\ldots,k\).

• (a)–(c): The results immediately follow by the very definition of the graph \(G_k\) and by Claim 1.
• (d): By Claim 1, \(d_G(v) \ge 2s r\). If the equality holds then \(N_G(u) \cap N_G(v)\) is empty. Since \(|N_{G_k}(u) \cap N_{G_k}(v)| \ge 2\), \(d_{G_k}(v) \ge 2s r + 2\). If \(d_G(v) = 2s r + 1\) then \(|N_G(u) \cap N_G(v)| \le 1\). Since \(|N_{G_k}(u) \cap N_{G_k}(v)| \ge 2\), \(d_{G_k}(v) \ge 2s r + 2\).
• (e): By Claim 1, \(d_G(v) \ge 2s 2\). If the equality holds then \(N_G(u) \cap N_G(v)\) is empty. Since \(|N_{G_k}(u) \cap N_{G_k}(v)| = 1\), \(d_{G_k}(v) \ge 2s 1\).

3. Upper bounds: degree s vertices

Motivated by Theorems A, B and C, in this section we concentrate on the set of all vertices of degree at most s in a 2-cell embedded graph, \(s \ge 4\). We impose some restrictions on this set to obtain new upper bounds on the bondage number. The main result of this section is the following theorem:

Theorem 3.1. Let G be a connected graph 2-cell embedded in \(\mathbb{M} \in \{\mathbb{S}_p, \mathbb{N}_q\}\). If \(V_s(G) \neq \emptyset\) for some \(s \geq 4\) and

\[-14\chi(\mathbb{M}) < (s-4)\beta_0(\langle V_s, G \rangle) + 2(s-5)|G| + 4|V_{\leq 2}| + 2\sum_{j=3}^{s-1} (5-j)|V_j|\]

then \(b(G) \leq B'(G) \leq 2s - 2\).

Proof. Let G be a connected graph 2-cell embedded in a surface M with χ(M) = χ. Suppose B0 (G) ≥ 2s − 1. Keeping the notation of Lemma 2.3 let us consider the graph H = G^k − V^≤s−1. By Clam 1 and Lemma 2.3 we immediately have:

Claim 2. Let I^s = I − V^≤s−1.

• (a) δ(H) = s, I^s = Vs(H) and I^s is an independent set of H.
• (b) If u ∈ V (H) − NG[I] then NH(u) = NG(u) and dH(u) ≥ s + 1.
• (c) If v ∈ NG(V^≤2) then dH(v) ≥ 2s − 2.
• (d) If v ∈ NG(Vl), 3 ≤ l ≤ s − 1, then dH(v) ≥ 2s − l + 1.
• (e) If v ∈ NG(Is), then dH(v) ≥ s + 2.

By Lemma 2.1 and Claim 2 it follows that

\[6(|H| - \chi) \geq 2||H|| = \sum_{v \in I_s} d_H(v) + \sum_{u \in N_G(I)} d_H(u) + \sum_{t \in V(H) - N_G[I]} d_H(t)\] \[\geq s|I_s| + ((s+2)|N_G(I_s)| + |V_{\leq 2}|(2s-2) + \sum_{j=3}^{s-1} (2s-j+1)|V_j|)\] \[+(s+1)(|H| - |I_s| - |N_H(I_s)| - |N_G(V_{\leq s-1})|)\]

or equivalently

\[-6\chi \ge -|I_s| + |N_H(I_s)| + (s-5)|H| + |V_{\le 2}|(s-3) + \sum_{j=3}^{s-1} (s-j)|V_j|.\] (3)

Let us consider the bipartite graph R with parts I^s and NH(Is), and edge set {uv ∈ E(G) | u ∈ Is, v ∈ NG(Is)}. First let R have a cycle. Lemma 2.1 implies s|Is| = kRk ≤ 2(|R| − χ). Since |R| = |Is| + |NH(Is)|, we obtain

\[|N_H(I_s)| \ge \frac{s-2}{2}|I_s| + \chi\] (4)

If R is a forest then s|Is| = kRk ≤ |R|−1 = |Is|+|NH(Is)|−1. Hence |NH(Is)| ≥ (s−1)|Is|+1 ≥ s−2 2 |Is| + χ.

By (3) and (4) it follows

\[-14\chi \ge (s-4)|I_s| + 2(s-5)|H| + 2|V_{\le 2}|(s-3) + 2\sum_{j=3}^{s-1}(s-j)|V_j|.\] (5)

Since |H| = |G| − |V^≤s−1|, we finally obtain

\[-14\chi \ge (s-4)|I_s| + 2(s-5)|G| + 4|V_{\le 2}| + 2\sum_{j=3}^{s-1} (5-j)|V_j|, \tag{6}\]

a contradiction.

The next two corollaries immediately follow from Theorem 3.1.

Corollary 3.1. Let G be a connected graph 2-cell embedded in \(\mathbb{M} \in \{\mathbb{S}_p, \mathbb{N}_q\}\).

• (i) If \(V_5(G) \neq \emptyset\) and \(-14\chi(\mathbb{M}) < 4|V_{<3}| + 2|V_4| + \beta_0(\langle V_5, G \rangle)\) then \(b(G) \leq B'(G) \leq 8\).
• (ii) If \(V_6(G) \neq \emptyset\) and \(-7\chi(\mathbb{M}) < 2|V_{<3}| + |V_4| + \beta_0(\langle V_6, G \rangle) + |G|\) then \(b(G) \leq B'(G) \leq 10\).
• (iii) If \(V_6(G) = \emptyset\), \(V_7(G) \neq \emptyset\) and \(-14\chi(\mathbb{M}) < 4|V_{\leq 3}| + 2|V_4| + 3\beta_0(\langle V_7, G \rangle) + 4|G|\) then \(b(G) \leq B'(G) \leq 12\).

This solves Conjecture 1 when (a) G is as in Corollary 3.1(i) and \(\Delta(G) \geq 6\) or (b) G is as in Corollary 3.1(ii) and \(\Delta(G) \geq 7\).

Corollary 3.2. Let G be a connected graph 2-cell embedded in \(\mathbb{M} \in \{\mathbb{S}_p, \mathbb{N}_q\}\), \(\delta(G) = \delta \geq 4\) and \(-14\chi(\mathbb{M}) < (\delta - 4)\beta_0(\langle V_\delta, G \rangle) + 2(\delta - 5)|G|\). Then \(b(G) \leq B'(G) \leq 2\delta - 2\).

Hence we may conclude that Conjecture 1 is true whenever G is as in Corollary 3.2 and \(4\delta(G)-4\leq 3\Delta(G)\).

Remark 3.1. Let G be a connected graph 2-cell embedded in a surface \(\mathbb M\) with \(\chi(\mathbb M)=\chi\leq -1\) and let \(\delta(G)=\delta\geq 6\). It is not hard to see that if \(-\frac{7\chi}{\delta-5}-\frac{(\delta-4)\beta_0(\langle V_\delta,G\rangle)}{2(\delta-5)}<|G|\leq -12\chi\) then the bound stated in Corollary 3.2 is better than that given in Theorem B(ii).

Theorem 3.2. Let G be a connected graph embeddable on a surface \(\mathbb{M}\) whose Euler characteristic \(\chi(\mathbb{M})\) is as large as possible. Let G have no vertices of degree \(\delta_{max}^{\mathbb{M}} = \max\{\delta(H) \mid a \text{ graph His 2-cell embedded in } \mathbb{M}\}\). Then (a) \(b(G) \leq B'(G) \leq 2\delta_{max}^{\mathbb{M}} - 3\), and (b) if \(\chi(\mathbb{M}) \leq 1\) then \(b(G) \leq B'(G) \leq 2\left\lfloor (5 + \sqrt{49 - 24\chi(\mathbb{M})})/2 \right\rfloor - 3\).

Proof. (a) Since \(\chi(\mathbb{M})\) is as large as possible, G has 2-cell embedding on \(\mathbb{M}\) [18]. Since G has no vertex of degree \(s = \delta_{max}^{\mathbb{M}}\), \(V_{\leq s-1}\) is not empty. Suppose to the contrary that \(B'(G) \geq 2s - 2\). Hence, for any two distinct vertices \(x, y \in V_{\leq s-1} = \{x_1, \ldots, x_k\}\), \(d_G(x, y) \geq 3\). Now, as in the proof of Lemma 2.3, we obtain a supergraph \(G_k\) for G with \(V(G) = V(G_k)\) and \(xy \in E(G_k) - E(G)\) implies both x and y are in \(N_G(u)\) for some \(u \in V_{\leq s}(G)\). Moreover, if \(d_G(x_r) \geq 3\) then \(\langle N_{G_k}(x_r), G_k \rangle\) is Hamiltonian, and if \(d_G(x_r) = 2\) then \(x_r\) belongs to a triangle of \(G_k\), \(r = 1, 2, \ldots, k\).

Claim 3.

• (i) If \(u \in V_r(G)\), \(3 \le r \le s 1\) and \(v \in N_G(u)\) then \(d_{G_k}(v) \ge 2s r + 1\).
• (ii) If \(u \in V_{\leq 2}(G)\) and \(v \in N_G(u)\) then \(d_{G_k}(v) \geq 2s 2\).

Proof of Claim 3. (i): Since \(B'(G) \ge 2s - 2\), \(d_G(v) \ge 2s - r - 1\). If the equality holds then \(N_G(u) \cap N_G(v)\) is empty. Since \(|N_{G_k}(u) \cap N_{G_k}(v)| \ge 2\), \(d_{G_k}(v) \ge 2s - r + 1\). If \(d_G(v) = 2s - r\) then \(|N_G(u) \cap N_G(v)| \le 1\). Since \(|N_{G_k}(u) \cap N_{G_k}(v)| \ge 2\), \(d_{G_k}(v) \ge 2s - r + 1\).

(ii): Since \(B'(G) \ge 2s - 2\), \(d_G(v) \ge 2s - d_G(u) - 1\). If \(d_G(u) = 2\) and the equality holds then \(N_G(u) \cap N_G(v)\) is empty. Since \(|N_{G_k}(u) \cap N_{G_k}(v)| = 1\), \(d_{G_k}(v) \ge 2s - 2\).

Figure 1. A planar graph F (without degree 5-vertices) having B(F) = B'(F) = 7.

Consider the graph \(H=G_k-V_{\leq s}(G)\) which is embedded in \(\mathbb{M}\). Since \(s\geq 5\), by Claim 3 it follows \(\delta(H)\geq s+1\) - a contradiction.

(b) The result immediately follows by (a) and Lemma F.

There are infinitely many planar graphs G without degree \(\delta_{max}^{\mathbb{S}_0}=5\) vertices for which \(B'(G)=2\delta_{max}^{\mathbb{S}_0}-3=7\). One such a graph is depicted in Figure 1. Notice that for a planar graph G without degree 5 vertices, the inequalities \(b(G)\leq 7\) and \(B(G)\leq 7\) are due to Kang and Yuan [16] and Huang and Xu [13], respectively.

By Theorem 3.2 and Corollary 3.1(i) it immediately follows:

Corollary 3.3. If G is 2-cell embedded in \(\mathbb{M} \in \{\mathbb{S}_0, \mathbb{N}_1\}\) then \(b(G) \leq B'(G) \leq 8\).

Figure 2. A planar triangulation H with B'(H) = 8.

The inequalities \(b(G) \le 8\) and \(B(G) \le 8\) for planar graphs, were proven by Kang and Yuan [16] and Huang and Xu [13], respectively. Consider the planar graph H shown in Figure 2 (this graph is taken from [13]). Each edge of H belongs to exactly 2 triangles, \(\delta(H) = 5\), \(\Delta(H) = 6\)

and all neighbors of any degree 5 (red) vertex are degree 6 (green) vertices. This implies B(H) = B'(H) = 8. Hence the upper bound for B'(G) in Corollary 3.3 is tight when \(\mathbb{M} = \mathbb{S}_0\).

Carlson and Develin [3] showed that there exist planar graphs with bondage number 6. It is not known whether there is a planar graph G with \(b(G) \in \{7, 8\}\).

Consider the projective-planar graph R depicted in Figure 3. Note that R is a triangulation, each edge of R is in exactly 2 triangles, \(\delta(R)=5\), there are no adjacent degree 5 (red) vertices and there is a degree 5 vertex adjacent to a degree 6 (black) vertex. This implies B(R)=B'(R)=8. Hence the upper bound for B'(G) in Corollary 3.3 is tight when \(\mathbb{M}=\mathbb{N}_1\). Note that in the case when \(\mathbb{M}=\mathbb{N}_1\), our result is better than \(b(G)\leq 10\) which was recently and independently obtained by Gagarin and Zverovich [7] and by the present author [25].

Figure 3. A projective-planar triangulation R with B'(R) = 8.

It is well known that the non-orientable genus of \(K_6\) is 1 [21]. Hence by Theorem E we obtain:

Proposition 3.1. There exist projective-planar graphs with bondage number 6. In particular, \(b(K_6 \circ K_1) = 6\).

Corollary 3.3 and Proposition 3.1 show that the maximum value of the bondage number of projective-planar graph is 6,7 or 8.

Question. Is there a projective-planar graph G with \(b(G) \in \{7, 8\}\)?

In the next corollary we improve the known upper bound for the bondage number of Klein bottle graphs from 11 (Gagarin and Zverovich [7]) to 9.

Corollary 3.4. Let G be 2-cell embedded in \(\mathbb{M} \in \{\mathbb{S}_1, \mathbb{N}_2\}\). Then \(b(G) \leq B'(G) \leq 9\). Moreover, B'(G) = 9 if and only if G is a 6-regular triangulation in \(\mathbb{M}\).

Proof. If \(\delta(G) \geq 6\) then G is a 6-regular triangulation as it follows by the Euler formula; hence B'(G) = 9. If \(V_5(G)\) is not empty then \(B'(G) \leq 8\) by Corollary 3.1. So, let \(V_{\leq 4}(G) \neq \emptyset\) and \(V_5(G) = \emptyset\). Suppose \(B'(G) \geq 9\). Note that if \(x \in V_r(G)\), \(r \leq 4\), \(y \in V(G)\) and \(1 \leq d_G(x,y) \leq 2\), then \(d_G(y) \geq 10 - r\). Hence \(V_3(G) \cup V_4(G) \neq \emptyset\) - otherwise each component of the graph \(G - V_{\leq 2}(G)\) is a graph with minimum degree at least 6 and maximum degree at least 7, contradicting Lemma 2.1. Consider the supergraph \(G_k\) of G described in Lemma 2.3, provided S = 1. Then Lemma 2.3 implies the graph S = 1 again a contradiction with Lemma 2.1.

It is an immediate consequence of Euler's formula that any 6-regular graph embedded in \(\mathbb{M} \in \{\mathbb{S}_1, \mathbb{N}_2\}\) is a triangulation. Altshuler [1] found a characterization of 6-regular toroidal graphs and Negami [19] characterized 6-regular graphs which embed in the Klein bottle. Moreover, no 6-regular graph embeds in both the torus and the Klein bottle [17]. The inequality \(b(G) \leq 9\) for toroidal graphs, was proven by Hou and Liu [10]. They also showed that there exist toroidal graphs with bondage number 7. The next result immediately follows by Theorem E.

Proposition 3.2. Let H be a 6-regular triangulation in \(\mathbb{M} \in \{\mathbb{S}_1, \mathbb{N}_2\}\). Then \(b(H \circ K_1) = 7\).

By Corollary 3.4 and Proposition 3.2 it immediately follows that the maximum value of the bondage number of graph embeddable on surface with Euler characteristic 0 is 7,8 or 9. The following question naturally arises.

Question. Is there a toroidal graph G with \(b(G) \in \{8, 9\}\)? Is there a Klein bottle graph G with \(b(G) \in \{8, 9\}\)?

Proposition 3.3. Let G be a connected toroidal or Klein bottle graph and let \(\mu \in \{b, b_2\}\).

• (i) If \(\mu(G) > \frac{3}{2}\Delta(G)\) then either \(4 \le \delta(G) \le \Delta(G) \le 5\) or G is 3-regular.
• (ii) If \(\mu(G) = \frac{3}{2}\Delta(G)\) then either G is 6-regular and no edge of G belongs to at least 3 triangles or \(3 \le \delta(G) \le \Delta(G) = 4\).

Proof. By Theorem D and Theorem A it follows that \(\mu(G) \leq \Delta(G) + 3\). Since G is 2-cell embedded, \(\Delta(G) \geq 3\).

• (i) Since \(\mu(G) > \frac{3}{2}\Delta(G)\), \(\Delta(G) \leq 5\). Assume \(\delta(G) \leq 3\). But then \(b_2(G) \geq \mu(G)\) implies that G is 3-regular.
• (ii) Since \(\mu(G) = \frac{3}{2}\Delta(G)\), \(\Delta(G) \in \{4,6\}\). If \(\Delta(G) = 6\) then \(b_2(G) \ge \mu(G) = 9 = \Delta(G) + 3\). By Theorem D, G is 6-regular and no edge of G belongs to at least 3 triangles. So, let \(\Delta(G) = 4\). Then \(\mu(G) = 6\) which leads to \(\delta(G) \ge 3\).

Problem 1. Find \(\max\{b(G) \mid G \text{ is a 6-regular triangulation in } \mathbb{M} \in \{\mathbb{S}_1, \mathbb{N}_2\} \text{ and no edge of } G \text{ belongs to at least 3 triangles}\}\). Find \(\max\{b(G) \mid G \text{ is a 4-regular graph embeddable in } \mathbb{M} \in \{\mathbb{S}_1, \mathbb{N}_2\}\}\).

For any graph G, which is embeddable in \(\mathbb{N}_3\), Gagarin and Zverovich [7] proved \(b(G) \leq 14\). We improve this bound in the following corollary.

Corollary 3.5. Let G be a graph embeddable in \(\mathbb{N}_3\). Then \(b(G) \leq B'(G) \leq 10\). If G has no degree 6 vertices then \(b(G) \leq B'(G) \leq 9\). If G has 15 mutually nonadjacent degree 5 vertices, then \(b(G) \leq B'(G) \leq 8\).

Proof. If G is embeddable in a surface with non-negative Euler characteristic then the result follows by Corollary 3.3 and Corollary 3.4. So, we may assume that the non-orientable genus of G is 3 and hence \(|G| \geq 7\). By Lemma 2.1, \(||G|| \leq 3|G| + 3\). Hence \(\delta_{max}^{\mathbb{N}_3} = 6\). If G has no degree 6 vertices then \(B'(G) \leq 9\) because of Theorem 3.2. Assume \(V_6\) is not empty. But then \(7 < \beta_0(\langle V_6, G \rangle) + |G|\). Now by Corollary 3.1(ii), \(b(G) \leq B'(G) \leq 10\). The rest immediately follows by Corollary 3.1(i).

Since the non-orientable genus of \(K_7\) is 3 [21], by Theorem E we obtain:

Proposition 3.4. There exist graphs embeddable on \(\mathbb{N}_3\) with bondage number 7. One of them is \(K_7 \circ K_1\).

Question. Is there a graph G embeddable in \(\mathbb{N}_3\) with \(b(G) \in \{8, 9, 10\}\)?

We conclude our results in this section with a constant upper bound on the bondage number of graphs embeddable in \(\mathbb{M} \in \{\mathbb{S}_2, \mathbb{N}_4\}\). For any such a graph \(G, b(G) \leq 16\) (Gagarin and Zverovich [7]). We improve this result as follows.

Corollary 3.6. Let G be a graph embeddable in \(\mathbb{M} \in \{\mathbb{S}_2, \mathbb{N}_4\}\). Then \(b(G) \leq 12\).

Proof. If G is embeddable in a surface with Euler characteristic not less than -1 then the result follows by Corollary 3.3, Corollary 3.4 and Corollary 3.5. So, we may assume that at least one of q(G) = 4 and h(G) = 2 holds. By Lemma 2.1, \(||G|| \le 3|G| + 6\). Hence \(\delta_{max}^{\mathbb{M}} \le 7\). Since \(h(K_8) = 2\) and \(q(K_8) = 4\), \(\delta_{max}^{\mathbb{M}} = 7\). If G has no degree 7 vertices then \(b(G) \le B'(G) \le 11\) because of Theorem 3.2. Assume \(V_7\) is not empty. If \(V_6\) is empty then Corollary 3.1(iii) implies \(b(G) \le B'(G) \le 12\). So, let \(V_6 \ne \emptyset\). If there are \(u \in V_6\) and \(v \in V_7\) which are at distance at most 2 then \(b(G) \le B'(G) \le b_1(G) \le 6 + 7 - 1 = 12\). If \(u \in V_6\), \(v \in V_7\) and \(d_G(u, v) \ge 3\) then \(|G| \ge 15\). By Corollary 3.1(ii), \(b(G) \le B'(G) \le 10\). □

Since \(h(K_8) = 2\) and \(q(K_8) = 4\) [21], by Theorem E we obtain:

Proposition 3.5. There exist graphs embeddable on \(\mathbb{N}_4\) with bondage number 8. There exist graphs embeddable on \(\mathbb{S}_2\) with bondage number 8. One such a graph is \(K_8 \circ K_1\).

Question. Is there a graph G embeddable in \(\mathbb{N}_4\) with \(b(G) \in \{9, 10, 11, 12\}\)? Is there a graph G embeddable in \(\mathbb{S}_2\) with \(b(G) \in \{9, 10, 11, 12\}\)?

4. Upper bounds: the domination number

In this section (a) we present upper bounds for the order of a graph in terms of the domination number and Euler characteristic, and (b) we give upper bounds for the bondage number in terms of the girth, domination number and Euler characteristic. The obtained bounds for b(G) are better than the one in Theorem C. We need the following results.

Theorem G. (Sanchis [26]) Let G be a connected graph with n vertices and domination number \(\gamma\) where \(3 \le \gamma \le n/2\). Then the number of edges of G is at most \((n - \gamma + 1)(n - \gamma)/2\). If G has exactly this number of edges and \(\gamma \ge 4\) it must be of the following form.

• \((P_1)\) An \((n-\gamma)\)-clique, together with an independent set of size \(\gamma\), such that each of the vertices in the \((n-\gamma)\)-clique is adjacent to exactly one of the vertices in the independent set, and such that each of these \(\gamma\) vertices has at least one vertex adjacent to it.
• \((P_2)\) For \(\gamma=3\), G may consist of a clique of n-5 vertices, together with 5 vertices \(x_1,x_2,x_3,x_4,x_5\), with edges \(x_1x_3\), \(x_2x_4\), \(x_2x_5\), such that every vertex in the (n-5)-clique is adjacent to \(x_4\) and \(x_5\), and in addition adjacent to either \(x_l\) or \(x_3\). Moreover, at least one of these vertices is adjacent to \(x_l\) and at least one to \(x_3\).

Theorem H. (Ore [20]) If G is a connected graph with \(n \ge 2\) vertices then \(\gamma(G) \le n/2\).

Proposition 4.1. Let G be a connected graph of order \(n \geq 2\) which is 2-cell embedded in a surface \(\mathbb{M}\).

• (i) If \(\gamma(G) = 2\) then \(n \ge 2 + \sqrt{6 2\chi(\mathbb{M})}\) when n is even and \(n \ge 2 + \sqrt{7 2\chi(\mathbb{M})}\) when n is odd.
• (ii) If \(\gamma(G) = \gamma \neq 2\) then

\[n \ge \gamma + (1 + \sqrt{9 + 8\gamma - 8\chi(\mathbb{M})})/2, \text{ and}\] (7)

\[\gamma \le n + (1 - \sqrt{8n + 9 - 8\chi(\mathbb{M})})/2.\] (8)

Proof. Since \(f(G) \ge 1\), Euler's formula implies \(n - ||G|| + 1 \le \chi(\mathbb{M})\).

• (i) If H is a graph with \(\gamma(H)=2\), |H|=n and maximum number of edges then its complement is a forest in which each component is a star [28]. This implies \(n(n-1)/2-\lceil n/2\rceil=\|H\|\geq \|G\|\). Hence \(n-n(n-1)/2+\lceil n/2\rceil+1\leq \chi(\mathbb{M})\). Equivalently, \(n^2-4n+2\chi(\mathbb{M})-2\geq 0\) when n is even and \(n^2-4n+2\chi(\mathbb{M})-3\geq 0\) when n is odd. Since \(n\geq 2\), the result easily follows.
• (ii) Since \(||G|| \le (n-\gamma+1)(n-\gamma)/2\) (by Theorem G when \(\gamma \ge 3\)), we have \(2\chi(\mathbb{M}) \ge 2n (n-\gamma+1)(n-\gamma) + 2\), or equivalently

\[n^2-(2\gamma+1)n+\gamma^2-\gamma-2+2\chi(\mathbb{M})\geq 0 \text{ and}\] \[\gamma^2-(2n+1)\gamma+n^2-n-2+2\chi(\mathbb{M})\geq 0.\]

Solving these inequalities we respectively obtain (7) and (8), because \(n \geq 2\gamma\) (by Theorem H). \(\Box\)

Next we show that the bounds in Proposition 4.1(ii) are tight. Let a graph G have property \((P_1)\)(Theorem G) and in addition \(\delta(G) \geq 4\), \(|G| = n = \gamma + i + 4t\), where \(t \geq \gamma = \gamma(G) \geq 4\), i = 1 when \(\gamma\) is odd, and i = 2 when \(\gamma\) is even. If \(p = (\|G\| - |G| + 1)/2\) then \(p = 4t^2 + t + (1 - \gamma)/2\) when \(\gamma\) is odd, and \(p = 4t^2 + 3t + 1 - \gamma/2\) when \(\gamma\) is even. Since G is clearly 4-edge connected, G can be embedded in \(\mathbb{M} = \mathbb{S}_p(\text{e.g.}\) see Jungerman [15]). Note also that G can be 2-cell embedded in \(\mathbb{N}_{2p}(\text{see}\) [21]). It is easy to see that, in both cases, we have equalities in (7) and (8).

Combining Theorem B(i) and Proposition 4.1 we immediately obtain the following results on the average degree of a graph.

Corollary 4.1. Let G be a connected graph 2-cell embedded in a surface M with χ(M) = χ ≤ −1.

• (i) Then ad(G) ^{≤ 6 − 12}χ/(3 + ^√ 17 − 8χ).
• (ii) If ^γ(G) = 2 then ad(G) ^{≤ 6 − 6}χ/(2 + ^√ 6 − 2χ) when |G| is even, and ad(G) ≤ 6 − ⁶χ/(2 + ^√ 7 − 2χ) when |G| is odd.
• (iii) If γ(G) = γ ≥ 3 and g(G) = g then

\[ad(G) \le \frac{2g}{g-2} (1 - \frac{2\chi}{2\gamma + 1 + \sqrt{9 + 8\gamma - 8\chi}})\]

\[\leq 6 - \frac{12\chi}{2\gamma + 1 + \sqrt{9 + 8\gamma - 8\chi}} \leq 6 - \frac{12\chi}{7 + \sqrt{33 - 8\chi}}.\]

The next theorem follows by combining Theorem B(ii) and Corollary 4.1.

Theorem 4.1. Let G be a connected graph 2-cell embedded in a surface M with χ(M) = χ ≤ −1.

(i) If γ(G) = 2 then

\[b(G) \leq 2ad(G) - 1 \leq 11 - \frac{12\chi}{2 + \sqrt{6 - 2\chi}}\] when \(|G|\) is even, and

\[b(G) \le 2ad(G) - 1 \le 11 - \frac{12\chi}{2 + \sqrt{7 - 2\chi}} \text{ when } |G| \text{ is odd.}\]

(ii) If γ(G) = γ ≥ 3 and g(G) = g then

\[b(G) \le 2ad(G) - 1 \le 3 + \frac{8}{g - 2} - \frac{8g}{g - 2} \cdot \frac{\chi}{2\gamma + 1 + \sqrt{9 + 8\gamma - 8\chi}}\]

\[\leq 11 - \frac{24\chi}{2\gamma + 1 + \sqrt{9 + 8\gamma - 8\chi}} \leq 11 - \frac{24\chi}{7 + \sqrt{33 - 8\chi}}.\]

Let us note that the bounds stated in Theorem 4.1 are better than the one in Theorem C whenever γ(G) ≥ 2. Finding a better upper bound for b(G) than the bound stated in Theorem 4.1(ii) could help answer the following question.

Question. What is the maximum number of edges in a connected graph of order n, domination number γ and girth g, where 1 ≤ γ ≤ n/2 and g ≥ 4.

5. Remarks

Teschner [29] proved that Conjecture 1 holds when the domination number of a graph G is not more than 3.

Theorem I. (Teschner [29]). Let G be a connected graph.

• (i) If γ(G) = 1 then b(G) = t 2 ≤ 1 ²∆(G) + 1 ≤ 3 ²∆(G), where t is the number of vertices of degree |G| − 1.
• (ii) If γ(G) = 2 then b(G) ≤ ∆(G) + 1 ≤ 3 ²∆(G).
• (iii) If γ(G) = 3 then b(G) ≤ 3 ²∆(G).

Hence it is naturally to turn our attention toward the graphs with the domination number at least 4. By Theorem 4.1(ii) we have

\[b(G) \le 2ad(G) - 1 \le 11 - \frac{24\chi}{9 + \sqrt{41 - 8\chi}}\]

whenever G is a connected graph 2-cell embedded in a surface M, χ(M) = χ ≤ −1 and γ(G) ≥ 4. For a graph G which has 2-cell embedding on a surface with Euler characteristic χ ∈ {−2, −3, . . . , −23}, we have the upper bounds shown in Table 1 provided γ(G) ≥ 4.

Table 1. Constant upper bounds for the bondage number of graphs: γ ≥ 4 and χ ∈ {−2, −3, . . . , −23}.

For the sake of completeness we add the upper bounds presented in section 3.

Table 2. Constant upper bounds for the bondage number of graphs: χ ≥ −2.

Recall that the only known connected graphs for which the equality in Teschner's conjecture holds are Kⁿ × Kn, n ≥ 2, and C3k+1, k ≥ 1. We conclude by:

Question. Is there a connected graph G such that G 6= Kn×Kn, G 6= C3k+1 and b(G) = ^{3 2}∆(G)?

References

• [1] A. Altshular, Construction and enumeration of regular maps on the torus, Discrete Math. 4 (1973), 201–217.
• [2] D. Bauer, F. Harary, J. Nieminen and C.L. Suffel, Domination alteration sets in graphs, Discrete Math. 47 (1983), 153–161.
• [3] K. Carlson and M. Develin, On the bondage number of planar and directed graphs, Discrete Math. 306 (2006), 820–826.
• [4] J.F. Fink, M.J. Jacobson, L.F. Kinch and J. Roberts, The bondage number of a graph, Discrete Math. 86 (1990), 47–57.
• [5] R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math. 4 (1970), 322–324.
• [6] A. Gagarin and V. Zverovich, Upper bounds for the bondage number of graphs on topological surfaces, Discrete Math. 313 (2013), 1132–1137.
• [7] A. Gagarin and V. Zverovich, The bondage number of graphs on topological surfaces and Teschner conjecture, Discrete Math. 313 (2013), 796–808.
• [8] B.L. Hartnell and D.F. Rall, Bounds on the bondage number of a graph, Discrete Math. 128 (1994), 173–177.
• [9] B.L. Hartnell and D.F. Rall, A bound on the size of a graph with given order and bondage number, Discrete Math. 197/198 (1999), 409–413.
• [10] J. Hou and G. Liu, A bound on the bondage number of toroidal graphs, Discrete Math. Algorithms Appl. 4 (3), Article ID 1250046 (2012), 5 pages.
• [11] F.-T. Hu and J.-M. Xu, On the complexity of the bondage and reinforcement problems, Journal of Complexity, 28 (2012), 192–201.
• [12] J. Huang, An improved upper bound for the bondage number of graphs on surfaces, Discrete Math. 312 (2012), 2776–2781.
• [13] J. Huang and J.-M. Xu, Note on Conjectures of Bondage Numbers of Planar Graphs, Applied Mathematical Sciences 6 (2012), 3277 – 3287
• [14] J. van den Heuvel, Personal communication.
• [15] M. Jungerman, A characterization of upper-embeddable graphs, Trans. Amer. Math. Soc. 241 (1978), 401–06.
• [16] L. Kang and J. Yuan, Bondage number of planar graphs, Discrete Math. 222 (2000), 191–198.
• [17] S. Lawrencenko and S. Negami, Constructing the graphs that triangulate both the torus and the Klein bottle, J. Combin. Theory Ser. B 77 (1999), 211–218.

• [18] B. Mohar and C. Thomassen, Graphs on surfaces, Johns Hopkins University Press, 2001.
• [19] S. Negami: Classification of 6-regular Klein-bottlal graphs. Res. Rep. Inf. Sci. T.I.T. A-96 (1984).
• [20] O. Ore, Theory of graphs, AMS Colloquium Publications 38. AMS 1962.
• [21] G. Ringel, Map Color Theorem, Springer-Verlag, Berlin, 1974.
• [22] G. Ringel, The combinatorial map color theorem, J. Graph Theory 1 (1977), 141–155.
• [23] H. Sachs, Einfuhrung in die Theorie der endlichen Graphen ¨ , Teil II, Teubner, Leipzig, 1972 (in German).
• [24] V. Samodivkin, Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces, Czechoslovak Math. Journal 63 (1) (2013), 191–204.
• [25] V. Samodivkin, Note on the bondage number of graphs on topological surfaces, Australas. J. Combin. 56 (2013), 183–186.
• [26] L. Sanchis, Maximum number of edges in connected graphs with a given domination number, Discrete Math. 87 (1991), 65–72.
• [27] S. Stahl, Generalized embedding schemes, J. Graph Theory 2 (1978), 41–52.
• [28] D. Sumner and P. Blitch, Domination critical graphs, J. Combin. Theory B 34 (1983), 65–76.
• [29] U. Teschner, A new upper bound for the bondage number of graphs with small domination number, Australas. J. Combin. 12 (1995), 27–35.
• [30] U. Teschner, The bondage number of a graph G can be much greater than ∆(G), Ars Combin. 43 (1996), 81–87.
• [31] J.-M Xu, On Bondage Numbers of Graphs a survey with some comments, International Journal of Combinatorics, 2013 (2013), Article ID 595210, 34 pages.