A new kind of parameter for fault tolerance of graphs. (3rd October 2018)

• Record Type: Journal Article
• Authors: Guo, Litao; Guo, Xiaofeng
• Other Names: Manogaran Gunasekaran guestEditor.; Chilamkurti Naveen guestEditor.; Hsu Ching‐Hsien guestEditor.; Vijayakumar V. guestEditor.
• Is Part Of: Concurrency and computation. Volume 31:Number 10(2019)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-10-03
• Subjects: diameter -- distance connectivity -- local connectivity -- path matrix; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4787
• Languages: English
• ISSNs: 1532-0626

Abstract

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.