Embedding index in some classes of graphs

M. Kamal Kumar and R. Murali
Notes on Number Theory and Discrete Mathematics, ISSN 1310–5132
Volume 21, 2015, Number 2, Pages 80–88
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 Gis either in S or adjacent to at least one vertex in S. A partition D = {D1, D2, …, Dk} of the vertex set of G is said to be a domatic partition or simply a d-partition of G if each class Diof 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 Gd(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

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

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

Comments are closed.