Nonsplit Domination Vertex Critical Graph

Document Type : Research Paper


1 PES University

2 Siddaganga Institute of technology


A dominating set D of a graph G = (V, E) is a nonsplit dominating set if the induced graph ⟨V − D⟩ is connected. The nonsplit domination number γns(G) is the minimum cardinality of a nonsplit domination set. The purpose of this paper is to initiate the investigation of those graphs which are critical in the following sense: A graph G is called vertex domination critical if γ(G − v) < γ(G) for every vertex v in G. A graph G is called vertex nonsplit critical if γns(G −v) < γns(G) for every vertex v in G. Initially we test whether some particular classes of graph are γns-critical or not and then we have shown that there is no existence of 2-γns-critical graph. Then 3-γns-critical graphs are characterized.


  1. P. David, summer and pattie blitch ,Domination critical graph, Journal of combinatorial theory series B, 34, (1983).
  2. F. Harary, Graph Theory, Addison-Wesley, reading Mass, (1969).
  3. V. R. Kulli, B. Janikiram, The nonsplit domination number of a graph, Indian J. Pure Appl. Math., 31, 545–550 (2000).
  4. M. Lemanska, A. Patyk, Weakly Connected Domination Critical graphs, Opuscula Mathematica, 28, 325–330 (2008).
  5. R. C. Brigham, P. Z. Chinn, R. D. Dutton, Vertex domination critical graphs, networks, 18, 173–179 (1988).
  6. D. P. Sumner, Critical concepts in domination, Discrete Math., 86, 33-46 (1990).
  7. X. Gang, L. Sun, D. Xiang, Connected Domination Critical graphs, Applied Mathematics, 17, 503–507 (2004).