Premium
Convexity of minimal total dominating functions in graphs
Author(s) -
Yu Bo
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199704)24:4<313::aid-jgt3>3.0.co;2-r
Subject(s) - mathematics , combinatorics , convexity , universality (dynamical systems) , graph , regular polygon , discrete mathematics , function (biology) , physics , geometry , quantum mechanics , evolutionary biology , financial economics , economics , biology
A total dominating function (TDF) of a graph G = ( V, E ) is a function f : V → [0, 1] such that for each v ϵ V , the sum of f values over the open neighborhood of v is at least one. Zero‐one valued TDFs are precisely the characteristic functions of total dominating sets of G . We study the convexity of minimal total dominating functions. A minimal total dominating function (MTDF) f is called universal if convex combinations of f and any other MTDF are minimal. Generalizing and unifying two previous major results by Cockayne, Mynhardt and Yu in the area, we give a stronger sufficiency condition for an MTDF to be universal. Moreover, we define a splitting operation on a graph G , which preserves the universality. Using the operation, we give many more classes of graphs having a universal MTDF. © 1997 John Wiley & Sons, Inc.