Structure of the set of all minimal total dominating functions of some classes of graphs

• Autorzy: K. Reji Kumar , Gary MacGillivray
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

Kategorie tematyczne

• 05C35: Extremal problems
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2010
• Tom: 30
• Numer: 3
• Strony: 407-423

Daty

wydano

2010

otrzymano

2009-02-19

poprawiono

2009-09-01

zaakceptowano

2009-09-01

Twórcy

autor

K. Reji Kumar

• Department of Mathematics, N.S.S College, Pandalam - 689 501, India

autor

Gary MacGillivray

• Department of Mathematics and Statistics, University of Victoria, BC, Canada

Bibliografia

• [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).

Identyfikatory

DOI

10.7151/dmgt.1503