Average distance in the strong product of graphs

作者：Casablanca Rocio M^*; Favaron Odile; Kouider Mekkia

来源：Utilitas Mathematica, 2014, 94: 31-48.

• Average distance
• transmission
• Wiener index
• hyper-Wiener index
• strong product

Let G be a connected graph of order n. The average distance mu(G) of G is the average of the distances between all ordered pairs of vertices of G and the transmission is sigma(G) = n(n-1)mu(G). We provide a general formulation of the transmission of the strong product G(1) boxed times G(2) of two connected graphs which gives in particular its exact value for the strong product of paths and cycles and in general some lower bounds. We prove that sigma(G(1) boxed times G2) <= sigma(P-n1 boxed times P-n2) where n(k) is the order of G(k). Our method allows to generalize two results related to the Wiener and hyper-Wiener indices of strong products of graphs by Pattabiraman and Paulraja, in Wiener and vertex PI indices of the strong product of graphs

• 出版日期2014-7