Graphs with Large Steiner Number
摘要
In 2002, G. Chartrand and P. Zhang [Discrete Math., 242, 4 (2002)] characterized the connected graphs G of order p ≥ 3 with Steiner number p, p − 1, or 2. We characterize all connected graphs G of order p ≥ 4 with Steiner number s(G) = p − 2. In addition, we obtain some sharp Nordhaus–Gaddum bounds for the Steiner number of connected graphs whose complement is also connected.