Journal of Jilin University Science Edition ›› 2024, Vol. 62 ›› Issue (3): 487-496.

Previous Articles     Next Articles

Fault Diameter of Strong Product Graph of Path and Star Graph

YUE Yuxiang1,2,3, LI Feng1   

  1. 1. College of Computer, Qinghai Normal University, Xining 810008, China; 2. The State Key Laboratory of Tibetan Intelligent Information Processing and Application, Xining 810008, China; 3. College of Information Engineering, Xinyang Vocational College of Art, Xinyang 464007, Henan Province, China
  • Received:2023-04-17 Online:2024-05-26 Published:2024-05-26

Abstract: Let the strong product graph of path Pm and star graph S1,n-1 be G=Pm*S1,n-1. Firstly, by inducing assumptions and constructing internally vertex or edge disjoint paths, combined with the centrality of star graph, the vertex fault diameter Dw(G) and edge fault diameter D′t(G) of the graph G were given. The results show that for any vertex or edge fault in the graph G, there holds Dw(G)≤d(G)+2 and D′t(G)≤d(G)+1. Secondly, through the unequal relation between the number of vertices and the number of edges, the upper bound of the vertex fault diameter of the strong product graph of two maximally connected graphs and the 
upper bound of the edge fault diameter of the strong product graph of two nontrivial connected graph were given.

Key words: path, star graph, strong product graph, vertex fault diameter, edge fault diameter

CLC Number: 

  • O157.5