M. Kamal Kumar and R. Murali

Notes on Number Theory and Discrete Mathematics, ISSN 1310-5132

Volume 21, 2015, Number 2, Pages 80—88

**Download full paper: PDF, 144 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, 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, …, *Dk*} of the vertex set of *G* is said to be a domatic partition or simply a *d*-partition of *G* if each class *Di*of *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 *θ*(*G*) . In this paper, we find the *θ*(*G*) for the Barbell graph, the Lollipop graph and the Tadpole graph.

### 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.
- Arumugam, S., Raja Chandrasekar, K. (2012) Minimal Dominating sets in Maximum domatic partitions, Australian Journal of Combinatorics, 52, 281–292.

## Related papers

## Cite this paper

APAKamal Kumar, M., & R. Murali (2015). Embedding index in some classes of graphs. Notes on Number Theory and Discrete Mathematics, 21(2), 80-88.

ChicagoM. Kamal Kumar, and R. Murali. “Embedding Index in Some Classes of Graphs.” Notes on Number Theory and Discrete Mathematics 21, no. 2 (2015): 80-88.

MLAM. Kamal Kumar, and R. Murali. “Embedding Index in Some Classes of Graphs.” Notes on Number Theory and Discrete Mathematics 21.2 (2015): 80-88. Print.