The criticality index of total domination of a path

Johannes H. Hattingh, Ernst J. Joubert, Lucas Van Der Merwe

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)285-291
Number of pages7
JournalUtilitas Mathematica
Publication statusPublished - Mar 2012

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Applied Mathematics


Dive into the research topics of 'The criticality index of total domination of a path'. Together they form a unique fingerprint.

Cite this