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
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 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.

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.