On the Wiener index, distance cospectrality and transmission-regular graphs

In this paper, we investigate various algebraic and graph theoretic properties of the distance matrix of a graph. Two graphs are D-cospectral if their distance matrices have the same spectrum. We construct infinite pairs of D-cospectral graphs with different diameter and different Wiener index. A gr...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2017-10, Vol.230, p.1-10
Main Authors: Abiad, Aida, Brimkov, Boris, Erey, Aysel, Leshock, Lorinda, Martínez-Rivera, Xavier, O, Suil, Song, Sung-Yell, Williford, Jason
Format: Article
Language:English
Subjects:
Diameter
Distance cospectral graphs
Distance matrix
Eigenvalues
Graph theory
Graphs
Laplacian matrix
Linear algebra
Lower bounds
Matrix
Transmission-regular
Trees (mathematics)
Wiener index
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we investigate various algebraic and graph theoretic properties of the distance matrix of a graph. Two graphs are D-cospectral if their distance matrices have the same spectrum. We construct infinite pairs of D-cospectral graphs with different diameter and different Wiener index. A graph is k-transmission-regular if its distance matrix has constant row sum equal to k. We establish tight upper and lower bounds for the row sum of a k-transmission-regular graph in terms of the number of vertices of the graph. Finally, we determine the Wiener index and its complexity for linear k-trees, and obtain a closed form for the Wiener index of block-clique graphs in terms of the Laplacian eigenvalues of the graph. The latter leads to a generalization of a result for trees which was proved independently by Mohar and Merris.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2017.07.010