Upper bound of embedding index in grid graphs

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
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₁, D₂, …, 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_i 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 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

1. Zelinka, B. (1980) Domatically critical graphs, Czechoslovak Math. L. 30(3), 486–489.
2. Rall, D. F. (1990) Domatically critical and domatically full graphs, Disc. Math. 86, 81–87.
3. Cockayne, E. L., & Hedetniemi, S. T. (1976) Disjoint independent dominating sets in graphs, Disc. Math. 15, 213–222.
4. Cockayne, E. L., & Hedetniemi, S. T. (1977) Towards a Theory of domination in graphs, Networks, 7, 247–261.
5. Harary, F. (1972) Graph Theory, Addison Wesley, Reading Mass.
6. Dirac, G. A. (1952) A property of 4-chromatic graphs and some remarks on critical graphs, Journal of London Mathematical Society, 27, 85–92.
7. Walikar, H. B., & Deshpande, A.P. (1994) Domatically critical graphs, Proc. of National Seminar on Recent Developments in Mathematics, Karnatak University, Dharwar, 27–30.
8. 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.
9. 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.
10. Walikar, H. B., & Acharya, B.D. (1979) Domination critical graphs, National academy of sciences, 2, 70–72.
11. Sudershan Reddy, L. (2006) The theory of domination in graphs & related topics, PhD Thesis, Karnatak University.
12. Kamal Kumar, M., & Murali, R. (2015) Embedding index in some class of graphs, Notes on Number Theory and Discrete Mathematics, 21(2), 80–88.
13. Arumugam, S., & Raja Chandrasekhar, K. (2012) Minimal Dominating sets in Maximum domatic partitions, Australian Journal of Combinatorics, 52, 281–292.