Non-split domination subdivision critical graphs

Girish V. R. and P. Usha
Notes on Number Theory and Discrete Mathematics, ISSN 1310-5132
Volume 23, 2017, Number 3, Pages 123—132
Download full paper: PDF, 154 Kb

Details

Authors and affiliations

Girish V. R.
Department of Mathematics, Siddaganga Institute of Technology
B. H. Road, Tumkur, Karnataka, India

P. Usha
Department of Mathematics, Siddaganga Institute of Technology
B. H. Road, Tumkur, Karnataka, India

Abstract

A set of vertices S is said to dominate the graph G if for each vS, there is a vertex uS with v adjacent to u. The minimum cardinality of any dominating set is called the domination number of G and is denoted by γ(G). A dominating set D of a graph G = (V, E) is a non-split dominating set if the induced graph ⟨VD⟩ is connected. The non-split domination number γns(G) is the minimum cardinality of a non-split 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 γ(Gv) < γ(G) for every vertex v in G. A graph G is called vertex non-split critical if γns(Gv) < γns(G) for every vertex v in G. Thus, G is kγns-critical if γns(G) = k, for each vertex vV(G), γns(G v) < k. A graph G is called edge domination critical if (G + e) < (G) for every edge e in G. A graph G is called edge non-split critical if γns(G + e) < γns(G) for every edge eG. Thus, G is kγns-critical if γns(G) = k, for each edge eG, γns(G + e) < k. First we have constructed a bound for a non-split domination number of a subdivision graph S(G) of some particular classes of graph in terms of vertices and edges of a graph G. Then we discuss whether these particular classes of subdivision graph S(G) are γns-critical or not with respect to vertex removal and edge addition.

Keywords

  • Domination number
  • Non-split domination
  • Non-split domination number
  • Critical graph
  • Subdivision graph
  • Vertex critical
  • Edge critical

AMS Classification

  • 05C69

References

  1. Sumner, D. P. & Blitch, P. (1983) Domination critical graph, Journal of combinatorial theory series B, 34, 65–76.
  2. Harary, F. (1969) Graph Theory, Addison-Wesley, Reading Mass.
  3. Kulli, V. R., & Janakiram, B. (2000) The Non-split domination of the graph, Indian J. Pure Appl.Math., 31, 545–550.
  4. Lemanska, M. & Patyk, A. (2008) Weakly connected domination critical graphs, Opuscula Mathematica, 28(3), 325–330.
  5. Brigham, R. C., Chinn, P. Z., & Dutton, R. D. (1988) Vertex domination critical graphs, Networks, 18(3), 173–179.
  6. Sumner, D. P. (1990) Critical concepts in Domination, Discrete Math., 86, 33–46.
  7. Haynes, T. W., Hedetniemi, S. T., & Slater, P. J. (1998) Fundamentals of Domination of graphs, Marcel Dekker, Inc. New York.
  8. Xue-Gang, Liang Sun, De-Xiang Ma. (2004) Connected Domination Critical graphs, Applied Mathematics, 17, 503–507.

Related papers

Cite this paper

Girish V. R., & Usha, P. (2017). Non-split domination subdivision critical graphs, Notes on Number Theory and Discrete Mathematics, 23(3), 123-132.

Comments are closed.