Printer Friendly

On open problems on the connected bicritical graphs.

[section]1. Introduction and preliminaries

In this paper, we concerned only with undirected simple graphs (loops and multiple edges are not allowed). All notations on graphs that are not defined here can be found in [7].

We denote the distance between two vertices x and y in G by [d.sub.G](x, y). The connectivity of G, written [kappa](G), is the minimum size of a vertex set S such that G-S is disconnected or has only one vertex. A graph G is k-connected if its connectivity is at least k. A graph is k-edge-connected if every disconnecting set of edges has at least k edges. The edge-connectivity of G, written [lambda](G), is the minimum size of a disconnecting set.

Let G = (V, E) be a graph. A set S [subset] V is a dominating set if every vertex in V is either in S or is adjacent to a vertex in S, that is V = [[union].sub.s [member of] S]N[s]. The domination number [gamma](G) is the minimum cardinality of a dominating set of G and a dominating set of minimum cardinality is called a [gamma](G) set.

A dominating set S is called an independent dominating set of G if no two vertices of S are adjacent. The minimum cardinality among the independent dominating sets of G is the independent domination number i(G) .

Note that removing a vertex can increase the domination number by more than one, but can decrease it by at most one. We define a graph G to be ([gamma], k)-critical, if [gamma](G-S)<[gamma](G) for any set S of k vertices. Obviously, a([gamma], k)-critical graph G has [gamma](G) [greater than or equal to] 2. The ([gamma], 1) bicritical graphs are precisely the domination critical graphs introduced by Brighman, Chinn, and Dutton. The ([gamma], 2)-critical graphs are precisely the domination bicritical graphs introduced by Brigham, Haynes, Henning, and Rall. We call a graph critical (respectively bicritical) if it is domination critical (respectively, domination bicritical). Further, we call a graph [gamma] critical (respectively [gamma]-bicritical) if it is domination critical (respectively, bicritical) with domination number [gamma]. For more details see [1-6].

The circulant graph [C.sub.n + 1]<1,4> is the graph with vertex set {[v.sub.0], [v.sub.1], ..., [v.sub.n]} and edge set {[v.sub.i][v.sub.i + j(mod n + 1)]|i [member of] {0,1, ..., n}} and j [member of] {1,4}.

The authors of [1] stated the following Observation and Problems:

Observation 1.1. For a bicritical graph G and x, y [member of] V(G), [gamma](G)-2 [less than or equal to] [gamma](G-{x, y}) [less than or equal to] [gamma](G)-1.

Problem 1. 1 [1] Is it true that every connected bicritical graph has a minimum dominating set containing any two specified vertices of the graphs?

Problem 1.2 [1] Is it true if G is a connected bicritical graph, then [gamma](G) = i(G), where i(G) is the independent domination number?

The Problem 1.2 is rejected by counterexample G = [C.sub.n + 1]<1,4> once n + 1 [equivalent to] 4(mod 9). We prove that the circulant graphs G = [C.sub.n + 1]<1,4> with n + 1 [equivalent to] k(mod 9) for k [member of] {3,4,8} are bicritical and [gamma](G-{x, y}) = [gamma](G)-1 for any pair x, y in V(G). We answer the question posed in Problem 1, in the affirmative for these graphs.

[section]2. Preliminary results

We verify domination number of certain graphs to achieve the main results.

Observation 2.1. Any 5k vertices such as {[v.sub.i], [v.sub.i + 1], ..., [v.sub.i + 5k-1]} from [C.sub.n + 1]<1,4>, cannot be dominated by any k vertices for which k [less than or equal to] n/5.

Lemma 2.1. Let G = ([C.sub.n + 1]<1,4>) be a circulant graph. Then the average of domination number is at most 9/2.

Proof. Let [v.sub.i] and [v.sub.j] be two vertices of a [gamma]-set S where i < j (mod n + 1) and for any k, (i < k < j), [v.sub.k] [not member of] S. There are some cases, once [v.sub.i], [v.sub.j] have common adjacent vertex or j-i = l(mod n + 1) where l [not member of] {1,2,3,4,5,8}.

Let [v.sub.i] and [v.sub.j] be adjacent or dominate a common vertex, i.e, l [member of] {1,2,3,4,5,8}, then they dominate at most 9 vertices.

Suppose that l [not member of] {1,2,3,4,5,8}. Let l = 6. Then the vertex [v.sub.i + 3] is not dominated by [v.sub.i] and [v.sub.j]. For dominating [v.sub.i + 3] there must be one of [v.sub.i + 7] or [v.sub.i-1] in S. Each of [v.sub.i + 7] or [v.sub.i-1] dominates at most three new vertices {[v.sub.i + 3], [v.sub.i + 8], [v.sub.i + 11]} or {[v.sub.i-5], [v.sub.i-2], [v.sub.i + 3]} respectively that have not been dominated by [v.sub.i], [v.sub.j]. So in this case, 3 vertices {[v.sub.i], [v.sub.j], [v.sub.i-1]} or {[v.sub.i], [v.sub.j], [v.sub.i + 7]} dominate 13 vertices.

Let l = 7. Then the vertices [v.sub.i + 2], [v.sub.i + 5] are not dominated by [v.sub.i] and [v.sub.j]. For dominating [v.sub.i + 2], [v.sub.i + 5] there must be two vertices [v.sub.i-2], [v.sub.i + 9] in S. Each of [v.sub.i-2] or [v.sub.i + 9] dominates four new vertices {[v.sub.i-6], [v.sub.i-3], [v.sub.i-2], [v.sub.i + 2]} or {[v.sub.i + 5], [v.sub.i + 9], [v.sub.i + 10], [v.sub.i + 13]} respectively. Hence 4 vertices {[v.sub.i], [v.sub.j], [v.sub.i-2], [v.sub.i + 9]} dominate 18 vertices.

Let l [not member of] {1,2,3,4,5,6,7,8}. Then the vertices {[v.sub.i + 2], [v.sub.i + 3], [v.sub.i + l-2], [v.sub.i + l-3]} are not dominated by [v.sub.i] and [v.sub.j]. For dominating these vertices the set S must contain the vertices {[v.sub.i-2], [v.sub.i-1], [v.sub.i + l + 1], [v.sub.i + l + 2]}. Theses four vertices dominate twelve new vertices {[v.sub.i-6], [v.sub.i-3], [v.sub.i + 2], [v.sub.i-5], [v.sub.i-2], [v.sub.i + 3], [v.sub.i + l-3], [v.sub.i + l + 2], [v.sub.i + l + 5], [v.sub.i + l-2], [v.sub.i + l + 3], [v.sub.i + l + 6]}. Thus six vertices {[v.sub.i], [v.sub.j], [v.sub.i-2], [v.sub.i-1], [v.sub.i + l + 1], [v.sub.i + l + 2]} dominate 22 vertices. Anyway, the average of domination number is at most 9/2.

Observation 2.2. Let G = [C.sub.n + 1]<1,4>) and n + 1 = 9m + k where 0 [less than or equal to] k [less than or equal to] 8 and [S.sub.1] = {[v.sub.9i], [v.sub.9i + 2]|0 [less than or equal to] i [less than or equal to] m-1}(mod n + 1). If k = 1, then [S.sub.1] dominates 9m-1 vertices. Otherwise [S.sub.1] dominates 9m vertices.

Proof. By Lemma 2.2, [S.sub.1] dominates the most vertices in the among sets of vertices with cardinality [absolute value of [S.sub.1]]. Let k [not equal to] 1. Any two vertices [v.sub.9i], [v.sub.9i + 2] dominates nine vertices {[v.sub.9i-4], [v.sub.9i-1], [v.sub.9i], [v.sub.9i + 1], [v.sub.9i + 4], [v.sub.9i-2], [v.sub.9i + 2], [v.sub.9i + 3], [v.sub.9i + 6]} (mod n + 1) and two vertices [v.sub.9(m-1) + 2], [v.sub.0] = [v.sub.9m + k] do not dominate any common vertex. Thus [S.sub.1] dominates 9m vertices. Now, let k = 1. Two vertices [v.sub.9(m-1) + 2], [v.sub.0] = [v.sub.9m + 1](mod n + 1) dominate a common vertex [v.sub.n-3], so 4 vertices [v.sub.0], [v.sub.2], [v.sub.9(m-1)] and [v.sub.9(m-1) + 2] dominate 17 vertices. Thus [S.sub.1] dominates 9m-1 vertices.

Observation 2.3. Let G = [C.sub.n + 1]<1,4>. Let [S.sub.1] be same as in the above Observation and [V.sub.1] be a subset vertices of V(G) that are dominated by [S.sub.1]. Then M = V(G)-[V.sub.1] is as follows.

If k = 0, then M = 0;. If k = 1, then M = {[v.sub.n-4], [v.sub.n-2]}. If k = 2, then M = {[v.sub.n-5], [v.sub.n-2]}. If k = 3, then M = {[v.sub.n-6], [v.sub.n-4], [v.sub.n-2]}. If k = 4, then M = {[v.sub.n-7], [v.sub.n-5], [v.sub.n-4], [v.sub.n-2]}. If k = 5, then M = {[v.sub.n-8], [v.sub.n-6], [v.sub.n-5], [v.sub.n-4], [v.sub.n-2]}. If k = 6, then M = {[v.sub.n-9], [v.sub.n- 7], [v.sub.n-6], [v.sub.n-5], [v.sub.n-4], [v.sub.n-2]}. If k = 7, then M = {[v.sub.n-10], [v.sub.n-8], [v.sub.n-7], [v.sub.n-6], [v.sub.n-5], [v.sub.n-4], [v.sub.n-2]}. If k = 8, then M = {[v.sub.n-11], [v.sub.n-9], [v.sub.n-8], [v.sub.n-7], [v.sub.n-6], [v.sub.n-5], [v.sub.n-4], [v.sub.n-2]}.

Now, we are ready to prove the following main theorem:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. Let G = [C.sub.n + 1]<1,4> with vertex set {[v.sub.0], [v.sub.1], ..., [v.sub.n]}. If G = [C.sub.13]<1,4>, obviously the set S = {[v.sub.0], [v.sub.6], [v.sub.7]} is a [gamma] set so [gamma]([C.sub.13]<1,4>) = 3.

By Lemma 2.1 and Observations 2.2, 2.3, for n + 1 = 9m + k where 0 [less than or equal to] k [less than or equal to] 8 the set [S.sub.1] = {[v.sub.9i], [v.sub.9i + 2]|0 [less than or equal to] i [less than or equal to] m-1} (mod n + 1) is a minimum dominating set for G-M where M has been specified by Observation 2.4 and [absolute value of [S.sub.1]] = 2 [[n+1]/9].

If n + 1 [equivalent to] 0(mod 9), then M = [empty set]; and [S.sub.1] is a [gamma]-set of G and [gamma](G) = 2 [n + 1/9].

If n + 1 [equivalent to] 1(mod 9), then M = {[v.sub.n-4], [v.sub.n-2]} and [S.sub.1] [union] {[v.sub.n-3]} is a [gamma]-set of G and [gamma](G) = 2[[n+1]/9] + 1.

If n + 1 [equivalent to] 2(mod 9), then M = {[v.sub.n-5], [v.sub.n-2]} and [S.sub.1] [union] {[v.sub.n-6]} is a [gamma]-set of G and [gamma](G) = 2 [[n+1]/9] + 1.

If n + 1 [equivalent to] 3(mod 9), then M = {[v.sub.n-6], [v.sub.n-4], [v.sub.n-2]} and [S.sub.1] [union] {[v.sub.n-4], [v.sub.n-6]} is a [gamma] set of G and [gamma](G) = 2 [[n+1]/9] + 2.

If n + 1 [equivalent to] 4(mod 9), then M = {[v.sub.n-7], [v.sub.n-5], [v.sub.n-4], [v.sub.n-2]} and [S.sub.1] [union] {[v.sub.n-4], [v.sub.n-6]} is a [gamma] set of G and [gamma](G) = 2 [[n+1]/9] + 2.

If n + 1 [equivalent to] 5(mod 9), then M = {[v.sub.n-8], [v.sub.n-6], [v.sub.n-5], [v.sub.n-4], [v.sub.n-2]} and [S.sub.1] [union] {[v.sub.n-4], [v.sub.n-6]} is a [gamma]-set of G and [gamma](G) = 2 [[n+1]/9[] + 2.

If n + 1 [equivalent to] 6(mod 9), then M = {[v.sub.n-9], [v.sub.n-7], [v.sub.n-6], [v.sub.n-5], [v.sub.n-4], [v.sub.n- 2]} and [S.sub.1] [union] {[v.sub.n-5], [v.sub.n-6]} is a [gamma]-set of G and [gamma](G) = 2[[n+1]/9] + 2.

If n + 1 [equivalent to] 7(mod 9), then M = {[v.sub.n-10], [v.sub.n-8], [v.sub.n-7], [v.sub.n-6], [v.sub.n-5], [v.sub.n-4], [v.sub.n-2]} and [S.sub.1] [union] {[v.sub.n-6], [v.sub.n-8]} is a [gamma]-set of G and [gamma](G) = 2 [[n+1]/9] + 2.

If n + 1 [equivalent to] 8(mod 9), then M = {[v.sub.n-11], [v.sub.n-9], [v.sub.n-8], [v.sub.n-7], [v.sub.n-6], [v.sub.n-5], [v.sub.n-4], [v.sub.n-2]} and [S.sub.1] [union] {[v.sub.n-5], [v.sub.n-6], [v.sub.n-7]} is a [gamma]-set of G and [gamma](G) = 2 [[n+1]/9] + 3.

[section]3. On the problems 1.1 and 1.2

In this section we discuss on the Problems 1.1 and 1.2.

Note that [gamma]([C.sub.13]<1,4>) = 3. It is easy to see that [gamma]([C.sub.13]<1,4>-{x, y})[greater than or equal to]3 for any x, y [member of] V([C.sub.n + 1]<1,4>), because [absolute value of V([C.sub.13]<1,4>-{x, y})] = 11. Hence the graph [C.sub.13]<1,4> is not bicritical.

Theorem 3.1. The graph [C.sub.n + 1]<1,4> is bicritical for n + 1 = 9m + 4, (m [greater than or equal to] 2) and n + 1 = 9m + 3, n + 1 = 9m + 8, (m [greater than or equal to] 1).

Proof. Let G = [C.sub.n + 1]<1,4> and V(G) = {0,1, ..., n}. Let S be a [gamma]-set of G as introduced in Theorem 2.5 and U be an arbitrary subset of V(G) with cardinality 2. It is sufficient to prove that [gamma](G - U) < [absolute value of S] for U = {x, y} and [d.sub.G](x, y) [less than or equal to] [[9m+k]/2] where k = 3,4,8, for another amounts it is symmetrically proved. Note that without loss of generality, we may assume that x = 0 and y is an arbitrary vertex which satisfies in [d.sub.G](0, y) [less than or equal to] [[9m+k]/2] (we provide the proof for y [member of] {1, ..., [[9m+k]/2]}). Let n + 1 = 9m + 3. First we prove for n + 1 [greater than or equal to] 30.

Let [F.sub.1] = [9t + 2/2] [absolute value of 3 [less than or equal to] t [less than or equal to] m}, [F.sub.2] = [9s + 2/2] + 2] 3 [less than or equal to] s [less than or equal to] m and s is odd } and [F.sub.3] = {5,7}.

Let U = {0, j} where j [member of] [F.sub.1]. Then j = 9l + 5 or j = 9l + 10 for some l. If j = 9l + 5 we assign [S.sub.0] = {9i + 5,9i + 7 [absolute value of 0 [less than or equal to] i [less than or equal to] l-1} [union] {j-3 = 9l + 2} [union] {j + 3 + 9k, j + 5 + 9k] 0 [less than or equal to] k [less than or equal to] m - (l + 1)} to G - U. If j = 9l + 10 we assign [S.sub.0] = {9i + 5,9i + 7|0 [less than or equal to] i[less than or equal to]l} [union] {j-3 = 9l + 7} [union] {j + 3 + 9k, j + 5 + 9k|0 [less than or equal to] k [less than or equal to] m-(l + 2)} [union] {n-1} to G - U.

Let U = {0, j} where j [member of] [F.sub.2]. Then j = 9l + 7 for some l. We assign [S.sub.0] = {9k + 3,9k + 5|0 [less than or equal to] k [less than or equal to] m-1} [union] {n-2} to G - U.

Let U = {0,5}. We assign [S.sub.0] = {3} [union] {9k + 10,9k + 12|0 [less than or equal to] k [less than or equal to] m - 2} [union] {10 + 9(m-1), 9m} to G - U.

Let U = {0,7}. We assign [S.sub.0] = {4} [union] {9k + 10,9k + 12|0 [less than or equal to] k [less than or equal to] m-2} [union] {9m, 9m + 1} to G - U.

Finally, let U = {0,j} where j [not member of] [F.sub.1] [union] [F.sub.2] [union] [F.sub.3]. We assign [S.sub.0] = {9k + 5,9k + 7|0 [less than or equal to] k [less than or equal to] m-1} [union] {9m + 1} to G - U.

It is easy to verify that [absolute value of [S.sub.0]] = 2[n/9] + 1 and all vertices of G - U are dominated by [S.sub.0]. Then, Theorem 2.5 implies that [gamma](G - U)<[gamma](G) , hence G is bicritical with [absolute value of V(G)] [greater than or equal to] 30.

Now, we show the truth of the two remaining cases: i.e. n + 1 = 12 and n + 1 = 21. For n + 1 = 12, we consider {2, 5, 7} with U = {0, j} and j [member of] {1,3,4,6,8,9,10,11}. Also we consider {3, 6, 9} with U = {0, j} and j [member of] {2,5,7}.

For n + 1 = 21, we assign [S.sub.0] = {5,7,14,16,19} to G - U with U = {0, j} and j [not member of] {5,7,14,16,19}. We consider [S.sub.0] = {3,7,9,16,18} for G - U with U = {0, j} and j [member of] {5,14}. Finally we assign [S.sub.0] = {3,5,12,14,18} to G - U with U = {0, j} and j [member of] {7,16,19}. Hence [absolute value of [S.sub.0]] = [absolute value of S]-1 for n + 1 = 9m + 3.

Let n + 1 = 9m + 4 [greater than or equal to] 22. Let F = [[9r+3]/2], [[9r+3]/2] + 2|r is odd and r [greater than or equal to] 1}.

Let U = {0, j} with j [member of] F [union] {2}. We assign [S.sub.0] = {9k + 5,9k + 7 [absolute value of 0 [less than or equal to] k[less than or equal to] m-1} [union] {n-1} to G - U. Finally, let U = {0, j} with j [not member of] F [union] {2}. We assign the set [S.sub.0] = {2} [union] {9k + 6,9k + 8] 0 [less than or equal to] k [less than or equal to] m-1} to G - U. It is easy to see that [absolute value of] [S.sub.0]| = [gamma]([C.sub.n + 1]<1,4>)-1 for n + 1 = 9m + 4.

Let n + 1 = 9m + 8. Let F = [[9r + 7]/2], [[9r + 7]/2] + 2|r is even and r[greater than or equal to] 0}.

Let U = {0,j} with j [member of] F. Then G - U is dominated by [S.sub.0] = {9k + j + 3,9k + j + 5|0 [less than or equal to] k [less than or equal to] m, (mod n + 1)}. Finally let j [not member of] F, we assign the set [S.sub.0] = {9k + 3,9k + 5|0 [less than or equal to] k [less than or equal to] m} to G - U. It is easy to see that 2m + 2 = [absolute value of [S.sub.0]] = [gamma]([C.sub.n + 1]<1,4>)-1 where n + 1 = 9k + 8.

Therefore [C.sub.n + 1]<1,4> is bicritical for n + 1 [member of] {9m + 3,9m + 4,9m + 8}.

As an immediate result we have the following that shows the above bound of Observation A is sharp for circulant bicritical graphs.

Corollary 3.1. Let G = [C.sub.n + 1]<1,4> be bicritical then [gamma](G-{x, y}) = [gamma](G)-1 where x, y [member of] V(G).

Theorem 3.2. The graph [C.sub.n + 1]<1,4> with n [greater than or equal to] 8 is not bicritical where n + 1 [equivalent to] l(mod 9) and l [member of] {0,1,2,5,6,7}.

Proof. Let S be the [gamma]-set of G = [C.sub.n + 1]<1,4> with structures in Lemma 2.1, Observations 2.2, 2.3 and Theorem 2.1. We consider the following.

Let n + 1 = 9m. Then [gamma](G) = 2n + 1/9 = 2m. If U = {x, y}, then [absolute value of V(G - U)] = n -1 = 9(m-1) + 7. Since the average domination number is at most 9/2, hence G - U is dominated by at least 2(m-1) + 2 = 2m vertices. Hence G is not bicritical for n + 1 = 9m.

Let n + 1 = 9m + 1. Then [gamma](G) = 2m + 1. Observation 2.3 implies that the set [S.sub.1] = {[v.sub.9i], [v.sub.9i + 2]|0 [less than or equal to] i [less than or equal to] m-1} (mod n + 1) dominates 9m-1 vertices V(G)-{[v.sub.n-4], [v.sub.n-2]} where [d.sub.G]([v.sub.n-4], [v.sub.n-2]) = 2 and any other set with 2m vertices with structure different from of [S.sub.1] dominates less than 9m-1 vertices of G. So, if U = {[v.sub.0], [v.sub.1]}, then G - U is not dominated by a set same as [S.sub.1], because [d.sub.G]([v.sub.0], [v.sub.1]) = 1. Hence G is not bicritical for n + 1 = 9m + 1.

Let n + 1 = 9m + 2. Then [gamma](G) = 2m + 1. Observation 2.3, implies that the set [S.sub.1] = {[v.sub.9i], [v.sub.9i + 2]|0 [less than or equal to] i [less than or equal to] m-1}(mod n + 1) dominates 9m vertices V(G)-{[v.sub.n-2], [v.sub.n-5]} where [d.sub.G]([v.sub.n-5], [v.sub.n-2]) = 3 and any other set with 2m vertices with different structure of [S.sub.1] dominates less than 9m vertices of G. So, if U = {[v.sub.0], [v.sub.1]}, then G - U is not dominated by a set same as [S.sub.1], because [d.sub.G]([v.sub.0], [v.sub.1]) = 1. Hence G is not bicritical for n + 1 = 9m + 2.

Finally, let n + 1 = 9m + k where k [member of] {5,6,7}. Then [gamma](G) = 2m + 2. Observations 2.3 and 2.4 imply that [S.sub.1] dominates 9m vertices of G-M where M has been specified in Observation 2.4. It is obviously seen that M-{[v.sub.n-4], [v.sub.n-5]} is not dominated by any one vertex. On the other hand any other set with 2m vertices with different structure of [S.sub.1] dominates less than 9m vertices of G. So 2m + 1 vertices cannot dominate G-{x, y} with [d.sub.G](x, y) = 1. Hence G is not bicritical for n + 1 = 9m + k where k [member of] {5,6,7}.

Theorem 3.3. Let G = [C.sub.n + 1]<1,4> with n + 1 [equivalent to] k (mod 9), k [member of] {3,4,8}. Then any pair of vertices are in some [gamma](G)-set.

Proof. Let n + 1 = 9m + k and 0 [less than or equal to] l [less than or equal to] [[m-1]/2];. It is sufficient to show that {0,9l + t} is in a [gamma](G) set for t [member of] {1,3,4,5,6,8} and given l, because of Theorem 2.5. We prove the result for k = 3 and the two other cases are similarly proved. The [gamma](G) set is [S.sub.1] [union] {n-4, n-6} for k = 3. One can substitute the set {n-4, n-6} with one of the sets {n, n-2}, {n-3, n-2}, {n-7, n-3}, {n-4, n-2} or {n-5, n-3}. Since 9l [member of] [S.sub.1] and [S.sub.1] [union] {n, n-2} is a [gamma] set it is easy to see that [S.sub.1] + 1 [union] {n + 1 = 0, n-1} is a [gamma]-set where [S.sub.1] + 1 = {s + 1(mod n + 1)| s [member of] [S.sub.1]}. Thus {0,9l + 1} is in a [gamma]-set

We also show that [S.sub.1] + 3 [union] {n-2 + 3 = 0, n-3 + 3 = n}, [S.sub.1] + 4 [union] {n-3 + 4 = 0, n-7 + 4}, [S.sub.1] + 5 [union] {n-4 + 5 = 0, n-2 + 4}, [S.sub.1] + 6 [union] {n-5 + 6 = 0, n-3 + 6} and [S.sub.1] + 8 [union] {n-7 + 8 = 0, n-3 + 8} are [gamma](G)-sets. Thus {0,9l + t} is in a [gamma](G)-set for t [member of] {1,3,4,5,6,8} and given l. We may use similar proofs, once n + 1 [equivalent to] 4 or 8(mod 9). Therefore G is a connected bicritical graph so that any two specified vertices are in a [gamma]-set.

We have shown that the answer to the question in Problem 1 is yes for [C.sub.n + 1]<1,4> with n + 1 [equivalent to] k(mod 9) , k [member of] {3,4,8}.

For providing the rejection of Problem 2, we first see an example.

Example 3.1. Let G = [C.sub.22]<1,4>. Then [gamma](G) [not equal to] i(G) . We verify this result as follows.

If a [gamma](G)-set contains {0,2}, then the set U = {5,7,8,9,10,11,12,13,14,15,16,17,19} has not been dominated by {0,2}.

If a [gamma](G)-set contains {0,3}, then the set U = {5,6,8,9,10,11,12,13,14,15,16,17,19,20} has not been dominated by {0,3}.

If a [gamma](G)-set contains {0,5}, then the set U = {2,3,7,8,10,11,12,13,14,15,16,17,19,20} has not been dominated by {0,5}.

If a [gamma](G)-set contains {0,6}, then the set U = {3,8,9,11,12,13,14,15,16,17,19,20} has not been dominated by {0,6}.

If a [gamma](G)-set contains {0,7}, then the set U = {2,5,9,10,12,13,14,15,16,17,19,20} has not been dominated by {0,7}.

If a [gamma](G)-set contains {0,8}, then the set U = {2,3,5,6,10,11,13,14,15,16,17,19,20} has not been dominated by {0,8}.

If a [gamma](G)-set contains {0,9}, then the set U = {2,3,6,7,11,12,14,15,16,17,19,20} has not been dominated by {0,9}.

If a [gamma](G)-set contains {0,10}, then the set U = {2,3,5,7,8,12,13,15,16,17,19,20} has not been dominated by {0,10}.

If a [gamma](G)-set contains {0,11}, then the set U = {2,3,5,6,8,9,13,14,16,17,19,20} has not been dominated by {0,11}.

Let {a, b} be any independent vertices in a [gamma](G)-set, then the situation of {a, b} will satisfy one of the above cases. It is also easy to see that the set U cannot be dominated by any four independent vertices of U. Thus [gamma](G) [not equal to] i(G) . Since G = [C.sub.22]<1,4> is a connected bicritical graph, so the answer to Problem 1.2 is "no".

In the following we exhibit a family of graphs for which the answer to Problem 1.2 is also "no".

Theorem 3.4. Let G = [C.sub.n + 1]<1,4> with n + 1 = 9m + 4(m [greater than or equal to] 2) . Then there is no [gamma](G)-set so that [gamma](G) = i(G).

Proof. Theorem 2.1 asserts that [S.sub.1] dominates G-M where M = {n-7, n-5, n-4, n-2} and [S.sub.1] [union] {n-4, n-6} is a [gamma](G)-set and any two independent vertices in M cannot dominate M. Hence by choosing [S.sub.1] one cannot have a [gamma]-set so that [gamma](G) = i(G) . If S is any independent vertex set with cardinality [absolute value of [S.sub.1]], then Lemma 2.1 and Observation 2.2 says if S dominates the vertex set [V.sub.1] of G then V(G)\[V.sub.1] cannot be dominated by two independent vertices. Therefore [gamma](G) [not equal to] i(G).

Remark 3.1. The Family of graphs G = [C.sub.n + 1]<1,4> with n + 1 = 9m + 3 and n + 1 = 9m + 8 are connected bicritical graphs with [gamma](G) = i(G). Because Theorem 2.5, shows that [S.sub.1] [union] {n-2, n-4} and [S.sub.1] [union] {n-2, n-5, n-7} are independent [gamma]-sets of [C.sub.9m + 3]<1,4> and [C.sub.9m + 8]<1,4> respectively.

[section]4. Diameter and vertex (edge) connectivity

Here, the diameter of [C.sub.n + 1]<1,4> is compared with the [gamma] set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof. We determine the diameter of ([C.sub.n + 1]<1,4>) as follows. If &RightFloor;n + 1/2[??] = 4k, k [greater than or equal to] 1 then diam ([C.sub.n + 1]<1,4>) = d([v.sub.0], [v.sub.4k-1]) = d([v.sub.0], [v.sub.4k]) + d([v.sub.4k], [v.sub.4k-1]) = k + 1.

If [[n+1]/2] = 4k + 1 then diam ([C.sub.n + 1]<1,4>) = d([v.sub.0], [v.sub.4k + 1]) = d([v.sub.0], [v.sub.4k]) + d([v.sub.4k], [v.sub.4k + 1]) = k + 1.

If [[n+1]/2] = 4k + 2 then diam ([C.sub.n + 1]<1,4>) = d([v.sub.0], [v.sub.4k + 2]) = d([v.sub.0], [v.sub.4k]) + d([v.sub.4k], [v.sub.4k + 2]) = k + 2.

If [[n+1]/2] = 4k + 3 then diam ([C.sub.n + 1]<1,4>) = d([v.sub.0], [v.sub.4k + 2]) = d([v.sub.0], [v.sub.4k]) + d([v.sub.4k], [v.sub.4k + 2]) = k + 2.

Theorem 4.2. (i) Let G = [C.sub.n + 1]<1,4>. Then diam(G) < [gamma](G) for n [not member of] {9,13}. (ii) ([gamma](G) - diam(G)) [right arrow] [infinity] once n [right arrow] [infinity].

Proof. For n = 9 and n = 13 it is clearly [gamma](G) = diam(G) . For another n, depending to the relation between 4 |[[n+1]/2], 4 [??][[n+1]/2], 4 |[[n+1]/2] - 1 or 4 [??] [[n+1]/2] - 1 with n + 1 [equivalent to] k(mod 9) in Theorems 2.1 and 3.3, we have the following.

For n = 8m, then n = 72t + r where r [member of] {0,8,16,24,32,40,48,56,64}. An easy calculation shows that [gamma](G)-diam(G) [member of] {7t + 2,7t + 3,7t + 4,7t + 5,7t + 6,7t + 7}.

For n = 8m + 1, then n = 72t + r where r [member of] {1,9,17,25,33,41,49,57,65}. So [gamma](G) - diam(G) [member of]{7t + 3,7t + 4,7t + 5,7t + 6,7t + 7}.

For n = 8m + 2, then n = 72t + r where r [member of] {2,10,18,26,34,42, 50, 58,66 }. So [gamma](G) - diam(G) [member of] {7t + 2,7t + 4,7t + 5,7t + 6,7t + 7,7t + 8}.

For n = 8m + 3, n = 72t + r where r [member of] {3,11,19,27,35,43,51,59,67}. So [gamma](G)diam - (G) [member of] {7t + 2,7t + 4,7t + 5,7t + 6,7t + 7}.

For n = 8m + 4, then n = 72t + r where r [member of] {4,12,20,28,36,44, 52,60,68 }. So [gamma](G) - diam(G) [member of] {7t + 2,7t + 3,7t + 5,7t + 6,7t + 7}.

For n = 8m + 5, then n = 72t + r where r [member of] {5,13,21,29,37,45,53,61,69}. So [gamma](G) - diam(G) [member of] {7t + 2,7t + 3,7t + 4,7t + 6,7t + 7}.

For n = 8m + 6, then n = 72t + r where r [member of] {6,14,22,30,38,46,54,62,70}. So [gamma]([C.sub.n + 1]<1,4>) - diam([C.sub.n + 1]<1,4>) [member of] {7t + 2,7t + 3,7t + 4,7t + 5,7t + 7}.

For n = 8m + 7, then n = 72t + r where r [member of] {7,15,23,31,39,47, 55,63, 71 }. So [gamma](G) - diam(G)[member of] {7t + 1,7t + 2,7t + 3,7t + 4,7t + 5,7t + 6}.

Thus we see that [gamma](G) > diam(G). Hence the result holds.

Since n [right arrow] [infinity] then t [right arrow] [infinity] therefore lim([gamma](G)-diam - (G))[right arrow] [infinity] as n [right arrow] [infinity]. Hence the desired result follows.

Now, we study the vertex and edge connectivity of [C.sub.n + 1]<1,4>. Recall that a classic well-known theorem [3] implies that for any graph G, [kappa](G) [less than or equal to] [lambda](G)[less than or equal to] [delta](G).

Theorem 4.3. [kappa]([C.sub.n + 1]<1,4>) = [lambda]([C.sub.n + 1]<1,4>) = 4.

Proof. Let G = [C.sub.n + 1]<1,4>. Since G is 4-regular, then [kappa](G) [less than or equal to] [lambda](G)[less than or equal to] [delta](G) = 4. Therefore it is sufficient to prove [kappa](G) [greater than or equal to] 4. Let U be a subset of V(G) with [absolute value of U] [less than or equal to] 3. We prove that G - U is connected. Since G has no cut vertex, so [absolute value of U] [greater than or equal to] 2. Consider u, v[member of] V(G)\U, the original circular arrangement has a clockwise u, v-path and a counterclockwise u, v-path along the circle. Let A and B be the sets of internal vertices on these two paths. Then A [intersection] U [less than or equal to] 1 or B [intersection] U [less than or equal to] 1. Since in G each vertex has edges to the next two vertices in a particular direction, deleting at most one vertex cannot block travel in that direction. Thus we can be find a u, v-path in G-S via the set A or B in which S has at most one vertex. So [kappa](G) [greater than or equal to] 4 and then [kappa](G) = [lambda](G) = 4.

Theorems 2.1, 3.1 and 4.3 imply that Problem 2 of [1] "if G is a connected bicritical graph, is it true that [lambda] [greater than or equal to] 3" is partially true.

References

[1] R. C. Brigham, T. W. Haynes, M. A. Henning, D. F. Rall, Bicritical domination, Discrete Mathematics, 305(2005), 18-32.

[2] T. W. Haynes, S. T. Hedetniem, P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New york, 1998.

[3] D. A. Mojdeh, P. Firoozi and R. Hasni, On connected ([gamma], k)-critical graphs, to appear, Australasian Journal of Combinatorics.

[4] D. A. Mojdeh, N. J. Rad, On an open problem concerning total domination critical graphs, Exposition Math., 25(2007), 175-179.

[5] J. B. Phillips, T. W. Haynes, P. J. Slater, A generalization of domination critical graphs, Utilitas Math., 58(2000), 129-144.

[6] D. P. Sumner, E. Wojcicka, Graphs critical with respect to the domination number, in: T. W. Haynes, S. T. Hedentiem, P. J. Slater (Eds), Domination in Graphs: Advanced Topics, Marcel Dekker, New york, 1998 (Chapter 16).

[7] D. B. West, Introduction to graph theory (Second Edition), Prentice Hall USA 2001.

D. A. Mojdeh ([dagger]), H. Abdollahzadeh Ahangar ([double dagger]) and S. S. Karimizad (#)

([dagger]) Department of Mathematics, University of Tafresh, Tafresh, Iran

([double dagger]) Department of Basic Science, Babol University of Technology, Babol, Iran

(#) Department of Mathematics, University of Mazandaran, Babolsar, Iran

E-mail: damojdeh@tafreshu.ac.ir ha.ahangar@nit.ac.ir
COPYRIGHT 2013 American Research Press
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Mojdeh, D.A.; Ahangar, H. Abdollahzadeh; Karimizad, S.S.
Publication:Scientia Magna
Article Type:Report
Geographic Code:7IRAN
Date:Mar 1, 2013
Words:6079
Previous Article:Filter on generalized topological spaces.
Next Article:Some properties of certain subclasses of univalent integral operators.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |