Discussiones Mathematicae Graph Theory 30(3) (2010) 407-423
doi: 10.7151/dmgt.1503

[BIBTex] [PDF] [PS]

STRUCTURE OF THE SET OF ALL MINIMAL TOTAL DOMINATING FUNCTIONS OF SOME CLASSES OF GRAPHS

K. Reji Kumar

Department of Mathematics
N.S.S College, Pandalam - 689 501, India
e-mail: rkkmaths@yahoo.co.in

Gary MacGillivray

Department of Mathematics and Statistics
University of Victoria, BC, Canada
e-mail: gmacgill@math.uvic.ca

Abstract

In this paper we study some of the structural properties of the set of all minimal total dominating functions (ℱT) of cycles and paths and introduce the idea of function reducible graphs and function separable graphs. It is proved that a function reducible graph is a function separable graph. We shall also see how the idea of function reducibility is used to study the structure of ℱT(G) for some classes of graphs.

Keywords: minimal total dominating functions (MTDFs), convex combination of MTDFs, basic minimal total dominating functions (BMTDFs), simplex, polytope, simplicial complex, function separable graphs, function reducible graphs.

2010 Mathematics Subject Classification: Primary 05C69;
Secondary 05C35.

References

[1] B. Grünbaum, Convex Polytopes (Interscience Publishers, 1967).
[2] E.J. Cockayne and C.M. Mynhardt, A characterization of universal minimal total dominating functions in trees, Discrete Math. 141 (1995) 75-84, doi: 10.1016/0012-365X(93)E0192-7.
[3] E.J. Cockayne, C.M. Mynhardt and B. Yu, Universal minimal total dominating functions in graphs, Networks 24 (1994) 83-90, doi: 10.1002/net.3230240205.
[4] E.J. Cockayne, C.M. Mynhardt and B. Yu, Total dominating functions in trees: Minimality and convexity, J. Graph Theory 19 (1995) 83-92, doi: 10.1002/jgt.3190190109.
[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
[6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs - Advanced Topics (Marcel Dekker, Inc., New York, 1998).
[7] K. Reji Kumar, Studies in Graph Theory - Dominating functions, Ph.D Thesis (Manonmaniam Sundaranar University, Tirunelveli, India, 2004).
[8] K. Reji Kumar, G. MacGillivray and R.B. Bapat, Topological properties of the set of all minimal total dominating functions of a graph, manuscript.
[9] D.B. West, Graph Theory : An introductory course (Prentice Hall, New York, 2002).

Received 19 February 2009
Revised 1 September 2009
Accepted 1 September 2009