A new kind of parameter for fault tolerance of graphs. (3rd October 2018) - Guo, Litao; Guo, Xiaofeng
Summary: Suppose that G  = ( V ( G ),   E ( G )) is a connected graph and D ( G ) is the diameter of G . For two distinct vertices a 1, b 1  ∈  V, κ ( a 1,   b 1 ), defined as local connectivity of a 1 and b 1, is the maximum value of independent paths from a 1 to b 1 in G . Similarly, λ ( a 1,   b 1 ) is local edge connectivity of a 1 and b 1 . For some t  ∈ [1,   D ( G )],  ∀  a 1, b 1  ∈  V, a 1 is distinct to b 1, and distance of a 1 and b 1 is d ( a 1,   b 1 ) =  t, if κ ( a 1,   b 1 ) or ( λ ( a 1,   b 1 )) =   min  { d ( a 1 ), d ( b 1 )}, then G is called t ‐distance optimally (edge) connected. For all integers 0 <  k  ≤  t, if G is k ‐distance optimally connected, then we call that G is t ‐distance local optimally connected. Similarly, we have the definition of t ‐distance local optimally edge connected graphs. The t ‐distance connectivity κ d ( G,   t ) of G is κ d G t = min κ a 1, b 1 : a 1, b 1 ∈ V, d a 1, b 1 = t . The distance connectivity of G is defined as κ d ( G ) = ( κ d ( G,  1),   κ d ( G,  2),  …,   κ d ( G,   D ( G ))). Then, λ d ( G,   t ) and λ d ( G ) can be defined similarly. Using the number of (edge) independent v i ‐ v j paths to replace the number 1, we generalize the adjacency matrix to the (edge) path matrix. In this research, we characterize the distance connectivity of graphs with D ( G ) ≤ 2, Cartesian product of k ‐regular graphs, and the regular graphs. We also determine the eigenvalues of path matrix of some graphs and give some problems about distance connectivity.