Shapley Distance and Shapley Index for Some Special Graphs

Zhendong Gu, Shuming Zhou, Jiafei Liu, Qianru Zhou, Dajin Wang

Research output: Contribution to journalArticlepeer-review

Abstract

The Shapley distance in a graph is defined based on Shapley value in cooperative game theory. It is used to measure the cost for a vertex in a graph to access another vertex. In this paper, we establish the Shapley distance between two arbitrary vertices for some special graphs, i.e., path, tree, cycle, complete graph, complete bipartite, and complete multipartite graph. Moreover, based on the Shapley distance, we propose a new index, namely Shapley index, and then compare Shapley index with Wiener index and Kirchhoff index for these special graphs. We also characterize the extremal graphs in which these three indices are equal.

Original languageEnglish
Article number2050012
JournalParallel Processing Letters
Volume30
Issue number4
DOIs
StatePublished - Dec 2020

Keywords

  • Kirchhoff index
  • Shapley distance
  • Shapley index
  • Shapley value
  • Wiener index

Fingerprint Dive into the research topics of 'Shapley Distance and Shapley Index for Some Special Graphs'. Together they form a unique fingerprint.

Cite this