Upper bounds for domination related parameters in graphs on surfaces

Peer review under responsibility of Kalasalingam University.

Abstract

In this paper we give tight upper bounds on the total domination number, the weakly connected domination number and the connected domination number of a graph in terms of order and Euler characteristic. We also present upper bounds for the restrained bondage number, the total restrained bondage number and the restricted edge connectivity of graphs in terms of the orientable/nonorientable genus and maximum degree.

Keywords:

• Total/(weakly) connected domination number
• (Total) restrained/Roman bondage number
• Euler characteristic
• Orientable/nonorientable genus

1 Introduction

All graphs considered in this paper are finite, undirected, loopless, and without multiple edges. We denote the vertex set and the edge set of a graph by and , respectively. For a vertex of , denotes the set of all neighbors of in and the degree of is . The minimum and maximum degrees among the vertices of are denoted by and , respectively. For , let and . The parameter is called the minimum edge-degree of . We let denote the subgraph of induced by a subset . The girth of a graph is the length of a shortest cycle in ; the girth of a forest is .

An orientable compact 2-manifold or orientable surface (see [1]) of genus is obtained from the sphere by adding handles. Correspondingly, a non-orientable compact 2-manifold or non-orientable surface of genus is obtained from the sphere by adding crosscaps. Compact 2-manifolds are called simply surfaces throughout the paper. The Euler characteristic is defined by , , and , . A connected graph is embeddable on a surface if it admits a drawing on the surface with no crossing edges. Such a drawing of on the surface is called an embedding of on . Notice that there can be many different embeddings of the same graph on a particular surface . An embedding of a graph on surface is said to be 2-cell if every face of the embedding is homeomorphic to a disc. The set of faces of a particular embedding of on is denoted by . The orientable genus of a graph is the smallest integer such that admits an embedding on an orientable topological surface of genus . The non-orientable genus of is the smallest integer such that can be embedded on a non-orientable topological surface of genus . Note that (a) every embedding of a graph on is 2-cell [2], and (b) if a graph has non-orientable genus then has 2-cell embedding on [3]. Let a graph be 2-cell embedded on a surface . Set , , and . The Euler’s formula states

Let be a non-trivial connected graph and . If is disconnected and contains no isolated vertices, then is called a restricted edge-cut of . The restricted edge-connectivity of , denoted by , is defined as the minimum cardinality over all restricted edge-cuts of . Besides the classical edge-connectivity , the parameter provides a more accurate measure of fault-tolerance of networks than the classical edge-connectivity (see [4]).

A subset of is dominating in if every vertex of has at least one neighbor in . The domination number of , denoted by , is the size of its smallest dominating set. When is connected, we say is a connected dominating set if is connected. The connected domination number of is the size of its smallest connected dominating set, and is denoted by . For a connected graph and any non-empty , is called a weakly connected dominating set of if the subgraph obtained from by removing all edges each joining any two vertices in is connected. The weakly connected domination number of is the minimum cardinality among all weakly connected dominating sets in . A total dominating set, abbreviated as TDS, of a graph is a set of vertices of such that every vertex in is adjacent to a vertex in . Every graph without isolated vertices has a TDS, since is such a set. The total domination number of , denoted by , is the minimum cardinality of a TDS of .

A set is a restrained dominating set if every vertex not in is adjacent to a vertex in and to a vertex in . Every graph has a restrained dominating set, since is such a set. The restrained domination number of , denoted by , is the minimum cardinality of a restrained dominating set of G. One measure of the stability of the restrained domination number of under edge removal is the restrained bondage number , defined in [5] by Hattingh and Plummer as the smallest number of edges whose removal from results in a graph with larger restrained domination number.

A set is a total restrained dominating set, denoted TRDS, if every vertex is adjacent to a vertex in and every vertex in is also adjacent to a vertex in . The total restrained domination number of , denoted by , is the minimum cardinality of a total restrained dominating set of . Note that any isolate-free graph has a TRDS, since is a TRDS. The total restrained bondage number of a graph with no isolated vertex, is the cardinality of a smallest set of edges for which (1) has no isolated vertex, and (2) . In the case that there is no such subset , we define .

A labeling is a Roman dominating function (or simply an RDF), if every vertex with has at least one neighbor with . Define the weight of an RDF to be . The Roman domination number of G is . The Roman bondage number of a graph is defined to be the minimum cardinality of all sets for which .

The rest of the paper is organized as follows. Section 2 contains known results. In Section 3 we give tight upper bounds on the total domination number, the weakly connected domination number and the connected domination number of a graph in terms of order and Euler characteristic. In Section 4, we present upper bounds on the restrained bondage number, the total restrained bondage number and the restricted edge connectivity of graphs in terms of the orientable/nonorientable genus and maximum degree.

2 Known results

We make use of the following results in this paper.

Theorem A

Esfahanian and Hakimi [6]

If is a connected graph with at least four vertices and it is not a star graph, then .

Theorem B

Hatting and Plummer [5]

If , then .

Theorem C

Rad, Hasni, Raczek and Volkmann [7]

Let be a connected graph of order , . Assume that has a path such that , and has no isolated vertex. Then .

Theorem D

Rad, Hasni, Raczek and Volkmann [7]

for .

Theorem E

Rad and Volkmann [8]

If is a graph, and a path of length 2 in , then .

Theorem F

Let be a connected graph of order and size .

(i)	( [9]) If , then .

(ii)	( [10]) If , then .

(iii)

( [11]) If , then .

Theorem G

Dunbar et al. [12]

If is a connected graph with vertices then .

The average degree of a graph is defined as .

Theorem H

Hartnell and Rall [13]

For any connected nontrivial graph , there exists a pair of vertices, say and , that are either adjacent or at distance 2 from each other, with the property that .

Theorem I

Samodivkin [14]

Let be a connected graph embeddable on a surface whose Euler characteristic is as large as possible and let the girth of is , . Then:

Let

Theorem J

Ivančo [15]

If is a connected graph of orientable genus and minimum degree at least 3, then contains an edge such that . Furthermore, if does not contain 3-cycles, then contains an edge such that .

Theorem K

Jendrol’ and Tuhársky [16]

If is a connected graph of minimum degree at least 3 on a nonorientable surface of genus , then contains an edge such that . Furthermore, if does not contain 3-cycles, then .

A path is a path of type if , , and .

Theorem L

Borodin, Ivanova, Jensen, Kostochka and Yancey [17]

Let be a planar graph with . If no 2 adjacent vertices have degree 3 then has a 3-path of one of the following types:

Theorem M

Let be a connected graph with vertices and edges.

(i)	( [1], [18]) If is not a tree then can be 2-cell embedded on .

(ii)	( [19]) If is a 4-edge connected, then can be 2-cell embedded on .

3 Connected, weakly connected and total domination

Theorem 1

Let be a connected graph of order and total domination number , which is 2-cell embedded on a surface . Then:

(i)

;

(ii)	when is even and when is odd.

Proof

Note that and . Since , Euler’s formula implies . By Theorem F(i) we have . Hence or equivalently

where when is even and when is odd. Solving these inequalities we respectively obtain the bounds stated in (i) and (ii).  ■

Next we show that the bounds in Theorem 1 are tight. Let , and be integers such that , and . Let us consider any graph which has the following form:

is obtained from by adding edges between the clique and the graph in such a way that each vertex in the clique is adjacent to exactly one vertex in and each component of has at least one vertex adjacent to a vertex in the clique.

Clearly, , and . Hence is an integer and can be 2-cell embedded in (by Theorem M(i)). Now, let in addition, . Then since is clearly 4-edge connected, Theorem M(ii) implies that can be embedded in . It is easy to see that, in both cases, the inequalities in Theorem 1 become equalities.

Theorem 2

Let be a connected graph of order which is 2-cell embedded on a surface . If then

(1) (2)

Proof

Since , Euler’s formula implies . Since (by Theorem F(ii)), we have , or equivalently

Solving these inequalities we respectively obtain (1) and (2), because (by Theorem G).  ■

The bounds in Theorem 2 are attainable. Let , and be integers such that and , where when is odd, and when is even. We consider an arbitrary graph which has the following form:

is the union of a clique of vertices, and an independent set of size , such that each of the vertices in the -clique is adjacent to exactly one of the vertices in the independent set, and such that each of these vertices has at least one vertex adjacent to it.

Obviously, , and . If then when is odd, and when is even. Hence is an integer and can be 2-cell embedded in , which follows by Theorem M(i). Now, let in addition, . Then since is clearly 4-edge connected, can be embedded in (by Theorem M(ii)). It is easy to see that, in both cases, we have equalities in (1) and (2).

Theorem 3

Let be a connected graph of order which is 2-cell embedded on a surface . If then(3)

Proof

Note that implies . By Theorem F(iii) we have . Hence by Euler’s formula or equivalently Since , it immediately follows (3(3) ).  ■

The bound in Theorem 3 is sharp. Let , and be integers such that and . We consider any graph which has the following form:

is the union of a clique of vertices, and a path of vertices, where each vertex in the clique is adjacent to exactly one of the endpoints of the path, and each endpoint has at least one clique vertex adjacent to it.

Clearly , , and . Now Theorem M(i) implies that can be 2-cell embedded in . Finally, it is easy to check that .

In ending this section we note that in [20], the present author proved analogous results for the ordinary domination number.

4 Bondage numbers and restricted edge connectivity

An excellent survey on bondage numbers can be found in [21].

Theorem 4

Let be a connected graph with .

(i)

Then .

(ii)	If is of orientable genus , then . Furthermore, if does not contain 3-cycles, then .

(iii)

If is of nonorientable genus , then . Furthermore, if does not contain 3-cycles, then .

(iv)

Then .

(v)	Let be embeddable on a surface whose Euler characteristic is as large as possible and let the girth of is , . Then:

Proof

(i) Since , there is a path in such that has no isolated vertices and . Now, by Theorem C we have .

(ii) Combining (i) and Theorem J we obtain the required.

(iii) The result follows by combining Theorem K and (i).

(iv) By Theorem D we know that whenever . Hence we may assume has nonadjacent vertices. Theorem H implies that there are 2 vertices, say and , that are either adjacent or at distance 2 from each other, with the property that . Since is connected and , there is a vertex such that or is a path. In either case by Theorem C we have .

(v) Theorem I and (iv) together imply the result.  ■

It is well known that the minimum degree of any planar graph is at most 5.

Theorem 5

Let be a planar graph with minimum degree , . Then .

Proof

There is a path such that , because of Theorem L. Since , has no isolated vertices. The result now follows by Theorem C.  ■

Problem 1

Find a sharp constant upper bound for the total restrained bondage number of a planar graph.

Theorem 6

Let be a nontrivial connected graph of orientable genus , non-orientable genus and minimum degree at least 3. Then

(i)

, and

(ii)	, provided does not contain 3-cycles.

Proof

By combining Theorems A and B with Theorems J and K we obtain the required inequalities.  ■

Akbari, Khatirinejad and Qajar [22] recently showed that the Roman bondage number of any planar graph is not more than 15. In case when the planar graph has minimum degree 5, we improve this bound by 1.

Theorem 7

Let be a planar graph with . Then .

Proof

By Theorem L there is a path such that . Since (Theorem E), the result follows.  ■

Results on the Roman bondage number of graphs on surfaces may be found in [23].

Notes

Peer review under responsibility of Kalasalingam University.