2016/08/06 by Michitaka Furuya, Furuya, Michitaka
Mathematics · #05C69 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C69
paper · pdf · doi:10.48550/arxiv.1608.02154
13 pages, 0 figures
arxiv created 2016/08/06 · arxiv updated 2016/08/09
The domination number of a graph G, denoted by γ(G), is the minimum cardinality of a dominating set of G. A vertex of a graph is called critical if its deletion decreases the domination number, and a graph is called critical if its all vertices are critical. A graph G is called weak bicritical if for every non-critical vertex x∈ V(G), G-x is a critical graph with γ(G-x)=γ(G). In this paper, we characterize the connected weak bicritical graphs G whose diameter is exactly 2γ(G)-2. This is a generalization of some known results concerning the diameter of graphs with a domination-criticality.