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 *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*–

*γ*-critical if

_{ns}*γ*(

_{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*–

*γ*-critical if

_{ns}*γ*(

_{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

*γ*-critical or not with respect to vertex removal and edge addition.

_{ns}### Keywords

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

### AMS Classification

- 05C69

### References

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

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