Authors and affiliations
A set of vertices S is said to dominate the graph G if for each v ∉ S, there is a vertex u ∈ S 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 ⟨V — D⟩ 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 γ(G − v) < γ(G) for every vertex v in G. A graph G is called vertex non-split critical if γns(G − v) < γns(G) for every vertex v in G. Thus, G is k–γns-critical if γns(G) = k, for each vertex v ∈ V(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 e ∈ G. Thus, G is k–γns-critical if γns(G) = k, for each edge e ∈ G, γ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.
- Domination number
- Non-split domination
- Non-split domination number
- Critical graph
- Subdivision graph
- Vertex critical
- Edge critical
- Sumner, D. P. & Blitch, P. (1983) Domination critical graph, Journal of combinatorial theory series B, 34, 65–76.
- Harary, F. (1969) Graph Theory, Addison-Wesley, Reading Mass.
- Kulli, V. R., & Janakiram, B. (2000) The Non-split domination of the graph, Indian J. Pure Appl.Math., 31, 545–550.
- Lemanska, M. & Patyk, A. (2008) Weakly connected domination critical graphs, Opuscula Mathematica, 28(3), 325–330.
- Brigham, R. C., Chinn, P. Z., & Dutton, R. D. (1988) Vertex domination critical graphs, Networks, 18(3), 173–179.
- Sumner, D. P. (1990) Critical concepts in Domination, Discrete Math., 86, 33–46.
- Haynes, T. W., Hedetniemi, S. T., & Slater, P. J. (1998) Fundamentals of Domination of graphs, Marcel Dekker, Inc. New York.
- Xue-Gang, Liang Sun, De-Xiang Ma. (2004) Connected Domination Critical graphs, Applied Mathematics, 17, 503–507.
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.