**M. Kamal Kumar and R. Murali**

Notes on Number Theory and Discrete Mathematics

Print ISSN 1310–5132, Online ISSN 2367–8275

Volume 22, 2016, Number 3, Pages 20—35

**Download full paper: PDF, 359 Kb**

## Details

### Authors and affiliations

M. Kamal Kumar

*Department of the Mathematics, CMR Institute of Technology
Bangalore 560037, India*

R. Murali

*Department of the Mathematics, Dr. Ambedkar Institute of Technology
Bangalore 560056, India*

### Abstract

A subset *S* of the vertex set of a graph *G* is called a dominating set of *G* if each vertex of *G* is either in *S* or adjacent to at least one vertex in *S*. A partition *D* = {*D*_{1}, *D*_{2}, …, *D _{k}*} of the vertex set of

*G*is said to be a domatic partition or simply a d-partition of

*G*if each class

*D*of

_{i}*D*is a dominating set in

*G*. The maximum cardinality taken over all d-partitions of G is called the domatic number of

*G*denoted by

*d*(

*G*). A graph

*G*is said to be domatically critical or

*d*-critical if for every edge

*x*in

*G*,

*d*(

*G–x*) <

*d*(

*G*), otherwise

*G*is said to be domatically non

*d*-critical. The embedding index of a non d-critical graph

*G*is defined to be the smallest order of a

*d*-critical graph

*H*containing

*G*as an induced subgraph denoted by

*q*(

*G*). In this paper, we find the upper bound of

*q*(

*G*) for grid graphs.

### Keywords

- Domination number
- Domatic partition
- Domatic number
*d*-Critical graphs

### AMS Classification

- 05C69

### References

- Zelinka, B. (1980) Domatically critical graphs,
*Czechoslovak Math. L.*30(3), 486–489. - Rall, D. F. (1990) Domatically critical and domatically full graphs,
*Disc. Math.*86, 81–87. - Cockayne, E. L., & Hedetniemi, S. T. (1976) Disjoint independent dominating sets in graphs,
*Disc. Math.*15, 213–222. - Cockayne, E. L., & Hedetniemi, S. T. (1977) Towards a Theory of domination in graphs
*, Networks*, 7, 247–261. - Harary, F. (1972)
*Graph Theory*, Addison Wesley, Reading Mass. - Dirac, G. A. (1952) A property of 4-chromatic graphs and some remarks on critical graphs,
*Journal of London Mathematical Society*, 27, 85–92. - Walikar, H. B., & Deshpande, A.P. (1994) Domatically critical graphs,
*Proc. of National Seminar on Recent Developments in Mathematics*, Karnatak University, Dharwar, 27–30. - Walikar, H. B., & Savitha Basapur (1996) Deficiency of non
*d-*critical graphs,*Proc. of National Workshop on Graph Theory and Its Applications*, Manomaniam Sundaranar University, Tirunelveli, Feb 21-27, 1996, 235–242. - Walikar, H. B. (1996) Domatically Critical and Co-critical Graphs,
*Proc. of National Workshop on Graph Theory and Its Applications*, Manomaniam Sundaranar University, Tirunelveli, Feb 21-27, 1996, 223–234. - Walikar, H. B., & Acharya, B.D. (1979) Domination critical graphs,
*National academy of sciences*, 2, 70–72. - Sudershan Reddy, L. (2006)
*The theory of domination in graphs & related topics*,*PhD Thesis*, Karnatak University. - Kamal Kumar, M., & Murali, R. (2015) Embedding index in some class of graphs,
*Notes on Number Theory and Discrete Mathematics*, 21(2), 80–88. - Arumugam, S., & Raja Chandrasekhar, K. (2012) Minimal Dominating sets in Maximum domatic partitions,
*Australian Journal of Combinatorics*, 52, 281–292.

## Related papers

## Cite this paper

Kamal Kumar, M., & Murali, R. (2016). Upper bound of embedding index in grid graphs, Notes on Number Theory and Discrete Mathematics, 22(3), 20-35.