The criticality index of total domination of a path

Abstract

For a graph G = (V, E), a set 5 ⊆ V is a total dominating set if every vertex in V is adjacent to some vertex in S. The minimum cardinality of any total dominating set is the total domination number of G, denoted γ _t(G). It is known that γ _t(G) - 2 ≤ γ _t(G + e) ≤ γ _t(G) for an arbitrary edge e ∈ E(Ḡ). The criticality index of an edge e ∈ E(Ḡ) is defined as ci(e) = γ _t(G) - γ _t(G + e), while the criticality index of G is defined as ci(G) = (Σ _e∈E(Ḡ) ci(e))/m(Ḡ). We determine the criticality index of paths.