Premium
Vertex domination‐critical graphs
Author(s) -
Fulman Jason,
Hanson Denis,
Macgillivray Gary
Publication year - 1995
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230250203
Subject(s) - combinatorics , domination analysis , vertex (graph theory) , mathematics , critical graph , graph , neighbourhood (mathematics) , discrete mathematics , line graph , graph power , mathematical analysis
A graph G is vertex domination‐critical if for any vertex v of G the domination number of G ‐ v is less than the domination number of G . If such a graph G has domination number γ, it is called γ‐critical. Brigham et al. studied γ‐critical graphs and posed the following questions: (1) If G is a γ‐critical graph, is | V | ≥ (δ + 1)(γ ‐ 1) + 1?(2) If a γ‐critical graph G has (Δ + 1)(γ ‐ 1) + 1 vertices, is G regular? (3) Does i = γ for all γ‐critical graphs? (4) Let d be the diameter of the γ‐critical graph G . Does d ≤ 2(γ ‐ 1) always hold? We show that the first and third questions have a negative answer and the others have a positive answer.