Some Classes Of 3- γc- critical Graph

Dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The min- imum number of vertices in a connected dominating set of G is called the connected domination number of G, and is denoted by γc(G). The purpose of this paper is to initiate an investigation of those graphs which are critical in the following sense: for each v, u ∈ V (G) with v not adjacent to u, γc(G + vu) <γ c(G). Thus, G is k- γc- critical if γc(G )= k and for each edge e not in E(G) ,γ c(G) <k . we give some classes of 3- γc- critical graph. G of G has vertex set V (G) and edge set {xy|{x, y }⊆ V (G) and xy is not in E(G)}. The degree, neighborhood, and closed neighborhood of a vertex v in the graph G are denoted by d(v) ,N (v) ,a ndN(v )= N (v) ∪ v, respectively. The minimum degree and maximum degree of the graph G are denoted by δ(G) and Δ(G), respectively. The set of the edges between two disjoint vertex sets A and B is denoted by E(A, B), the subgraph induced by A in G by G(A) and G-A stands for G(V (G)\A). A hamiltonian path of G is a path passing exactly once through every vertex of G.A hamiltonian cycle is a closed hamiltonian path. The circumference c(G) is the length of a longest cycle of G. The graph G is hamiltonian if its circumference is equal to n. An independent set is a set of pairwise nonadjacent vertices, and the independence number α(G) is the maximum cardinality of an independent set. The independent domination number i(G) is the minimum cardinality of an independent set which dominates G. It is well known that in any graph G, γ(G) ≤ i(G) ≤ α(G) .I f A and B are two vertex sets of G, we say that A dominates B if every vertex of B\A has at least one neighbor in A. (When A or B is reduced to one vertex a or b, we simply write a dominates B or A dominates b.) A dominating set S is a set of vertices where every vertex of G is in N (v) for some v ∈ S. The domination numberγ(G) is the minimum cardinality of a dominating set. A dominating set in ag raphG is a connected dominating set of G if it induces a connected subgraph of G. The connected domination number γc(G) is the minimum cardinality of a connected dominating set. If S is a minimum connected dominating set, we call S a γc− set of G. A graph is said to be γ-domination critical, or just γ -critical, if γ(G )= γ and γ(G + e )= γ − 1 for every edge e in the complement ¯ Go fG. This concept of γ - critical graphs has been studied by Sumner and Blitch (1), Sumner (2), and Wojcicka (3). Haynes, Mynhardt and van der Merwe (4,5) defined a graph G to be total domination edge critical, or simply kt- critical, if γt(a + e) <γ t(G )= k for any edge e ∈ E( ¯ G).