The communicability distance in graphs

Research output: Contribution to journalArticle

20 Citations (Scopus)

Abstract

Let G be a simple connected graph with adjacency matrix A. The communicabilityGpq between two nodes p and q of the graph is defined as the pq-entry of G=exp(A). We prove here that ξp,q=(Gpp+Gqq-2Gpq)1/2 is a Euclidean distance and give expressions for it in paths, cycles, stars and complete graphs with n nodes. The sum of all communicabilitydistances in a graph is introduced as a new graph invariant ϒ(G). We compare this index with the Wiener and Kirchhoff indices of graphs and conjecture about the graphs with maximum and minimum values of this index.
Language English 4317-4328 12 Linear Algebra and its Applications 436 11 10.1016/j.laa.2012.01.017 Published - 1 Jun 2012

Fingerprint

Distance in Graphs
Stars
Graph in graph theory
Graph Invariants
Star Graph
Vertex of a graph
Euclidean Distance
Simple Graph
Complete Graph
Connected graph
Cycle
Path

Keywords

• matrix functions
• Euclidean distance
• graph spectrum
• graph distance
• communicability

Cite this

Estrada, Ernesto. / The communicability distance in graphs. In: Linear Algebra and its Applications. 2012 ; Vol. 436, No. 11. pp. 4317-4328.
@article{3c0c78b5097a42ceb7b7a5b54b1835cc,
title = "The communicability distance in graphs",
abstract = "Let G be a simple connected graph with adjacency matrix A. The communicabilityGpq between two nodes p and q of the graph is defined as the pq-entry of G=exp(A). We prove here that ξp,q=(Gpp+Gqq-2Gpq)1/2 is a Euclidean distance and give expressions for it in paths, cycles, stars and complete graphs with n nodes. The sum of all communicabilitydistances in a graph is introduced as a new graph invariant ϒ(G). We compare this index with the Wiener and Kirchhoff indices of graphs and conjecture about the graphs with maximum and minimum values of this index.",
keywords = "matrix functions, Euclidean distance, graph spectrum, graph distance, communicability",
author = "Ernesto Estrada",
year = "2012",
month = "6",
day = "1",
doi = "10.1016/j.laa.2012.01.017",
language = "English",
volume = "436",
pages = "4317--4328",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",
number = "11",

}

The communicability distance in graphs. / Estrada, Ernesto.

In: Linear Algebra and its Applications, Vol. 436, No. 11, 01.06.2012, p. 4317-4328.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The communicability distance in graphs

AU - Estrada, Ernesto

PY - 2012/6/1

Y1 - 2012/6/1

N2 - Let G be a simple connected graph with adjacency matrix A. The communicabilityGpq between two nodes p and q of the graph is defined as the pq-entry of G=exp(A). We prove here that ξp,q=(Gpp+Gqq-2Gpq)1/2 is a Euclidean distance and give expressions for it in paths, cycles, stars and complete graphs with n nodes. The sum of all communicabilitydistances in a graph is introduced as a new graph invariant ϒ(G). We compare this index with the Wiener and Kirchhoff indices of graphs and conjecture about the graphs with maximum and minimum values of this index.

AB - Let G be a simple connected graph with adjacency matrix A. The communicabilityGpq between two nodes p and q of the graph is defined as the pq-entry of G=exp(A). We prove here that ξp,q=(Gpp+Gqq-2Gpq)1/2 is a Euclidean distance and give expressions for it in paths, cycles, stars and complete graphs with n nodes. The sum of all communicabilitydistances in a graph is introduced as a new graph invariant ϒ(G). We compare this index with the Wiener and Kirchhoff indices of graphs and conjecture about the graphs with maximum and minimum values of this index.

KW - matrix functions

KW - Euclidean distance

KW - graph spectrum

KW - graph distance

KW - communicability

UR - http://www.scopus.com/inward/record.url?scp=84863320828&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2012.01.017

DO - 10.1016/j.laa.2012.01.017

M3 - Article

VL - 436

SP - 4317

EP - 4328

JO - Linear Algebra and its Applications

T2 - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

IS - 11

ER -