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 language | English |
---|---|
Pages (from-to) | 175-184 |
Number of pages | 10 |
Journal | Discrete Mathematics |
Volume | 161 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 5 Dec 1996 |
Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics