Realizability of the total domination criticality index

Abstract

For a graph G = (V, E), a set S ⊆ V is a total dominating set if every vertex in V is adjacent to some vertex in S. The smallest cardinality of any total dominating set is the total domination number _γt(G). For an arbitrary edge e εE(Ḡ), _γt(G) - 2 ≤ _γt(G + e) ≤ _γt(G); if the latter inequality is strict for each e ε E(Ḡ) ≠ φ, then G is said to be _γt-critical. The criticality index of an edge e ε E(Ḡ) is _γt(e) = _γt(G) - _γt(G + e). Let E(Ḡ) = [e₁...,e_m} and S = ∑_j=1^m̄ci(e_j). The criticality index of G is ci(G) = S/m̄. For any rational number k, 0 ≤ k ≤ 2, we construct a graph G with ci(G) = k. For 1 ≤ k ≤ 2, we construct graphs with this property that are _γt-critical as well as graphs that are not _γt-critical.