DMGT

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

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