The convexity graph of minimal total dominating functions of a graph

S. Arumugam ; Sithara Jerry

Kragujevac Journal of Mathematics, Tome 36 (2012) no. 1, p. 119

Résumé

Let $G=(V,E)$ be a graph without isolated vertices. A function $f:V\rightarrow [0,1]$ is a total dominating function if $\sum\limits_{u\in N(v)}f(u)\geq 1$ for all $v\in V$. A total dominating function $f$ is called a minimal total dominating function (MTDF) if any function $g:V\rightarrow [0,1]$ with $g0\}$ is the positive set of $f$ and $B_f=\{v\in V: \sum\limits_{u\in N(v)}f(u)=1\}$ is the boundary set of $f$. The relation $\rho$ defined on the set $\mathcal{F}$ of all MTDFs of $G$ by $f\rho g$ if $P_f=P_g$ and $B_f=B_g$ is an equivalence relation which partitions $\mathcal{F}$ into a finite number of equivalence classes $X_1,X_2,\dots,X_t$. The total convexity graph $\mathcal{C}_T(G)$ of $G$ has $\{X_1,X_2,\dots,X_t\}$ as its vertex set and $X_i$ is adjacent to $X_j$ if there exist $f\in X_i$ and $g\in X_j$ such that any convex combination of $f$ and $g$ is an MTDF of $G$. In this paper we determine the total convexity graphs of some standard graphs.

Détail

Classification : 05C69
Keywords: Total dominating function, minimal total dominating function, total convexity graph.