On the g-good-neighbor connectivity of graphs

Connectivity and diagnosability are two important parameters for the fault tolerant of an interconnection network G. In 1996, Fàbrega and Fiol proposed the g-good-neighbor connectivity of G. In this paper, we show that 1≤κg(G)≤n−2g−2 for 0≤g≤{Δ(G),⌊n−32⌋}, and graphs with κg(G)=1,2 and trees with κg(Tn)=n−t for 4≤t≤n+22 are characterized, respectively. In the end, we get the three extremal results for the g-good-neighbor connectivity.