On the g-good-neighbor connectivity of graphs

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