Local edge domination critical graphs

Michael A. Henning, Ortrud R. Oellermann, Henda C. Swart

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

Sumner and Blitch defined a graph G to be k-γ-critical if γ(G) = k and γ(G + uv) = k - 1 for each pair u, v of nonadjacent vertices of G. We define a graph to be k-(γ, d)-critical if γ(G) = k and γ(G + uv) = k - 1 for each pair u, v of nonadjacent vertices of G that are at distance at most d apart. The 2-(γ, 2)-critical graphs are characterized. Sharp upper bounds on the diameter of 3-(γ, 2)-and 4-(γ, 2)-critical graphs are established and partial characterizations of 3-(γ, 2)-critical graphs are obtained.

Original languageEnglish
Pages (from-to)175-184
Number of pages10
JournalDiscrete Mathematics
Volume161
Issue number1-3
DOIs
Publication statusPublished - 5 Dec 1996
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Local edge domination critical graphs'. Together they form a unique fingerprint.

Cite this