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

DOI10.1016/J.DAM.2017.07.010MaRDI QIDQ2399284zbMATH OpenOpenAlexFDO

Authors Aida Abiad, Boris Brimkov, Aysel Erey, Lorinda Leshock, Suil O, S. Y. Song, Xavier Martinez-Rivera, Jason S. Williford

Publication date 22 August 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.06911

zbMATH Keywords

diameterdistance cospectral graphsdistance matrixLaplacian matrixtransmission-regularWiener index

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: 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.

Recommendations

• On the largest distance (signless Laplacian) eigenvalue of non-transmission-regular graphs
• A relation between \(D\)-index and Wiener index for \(r\)-regular graphs
• Distance spectral radius of some k-partitioned transmission regular graphs
• Two Laplacians for the distance matrix of a graph
• On the sum of the generalized distance eigenvalues of graphs

Cites work

• A characterization of block graphs
• A construction of distance cospectral graphs
• Algorithms for graphs of bounded treewidth via orthogonal range searching
• An edge version of the matrix-tree theorem and the wiener index
• Average distance in weighted graphs
• Bipartite graphs with balanced (a,b)-partitions
• Contraction formulas for the Kirchhoff and Wiener indices
• Distance spectra of graphs: a survey
• Distance spectrum of graph compositions
• Eigenvalues, diameter, and mean distance in graphs
• Estimating the distance Estrada index
• Extremal Wiener index of trees with given number of vertices of even degree
• Forbidden minors for the class of graphs G with (G) 2
• scientific article; zbMATH DE number 5005356 (Why is no real title available?)
• scientific article; zbMATH DE number 3627232 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 6750341 (Why is no real title available?)
• Mathematical aspects of Wiener index
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Minimizing Wiener index for vertex-weighted trees with given weight and degree sequences
• On distance-balanced graphs
• On the Addressing Problem for Loop Switching
• On the largest eigenvalue of the distance matrix of a tree
• On the Wiener index of trees with given number of branching vertices
• On Wiener index of common neighborhood graphs
• Orientations of graphs with maximum Wiener index
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• Sharp bounds on the distance spectral radius and the distance energy of graphs
• Strongly distance-balanced graphs and graph products
• Subclasses of \(k\)-trees: characterization and recognition
• The distance spectrum of a tree
• The edge-Wiener index of benzenoid systems in linear time
• The graphs for which the maximum multiplicity of an eigenvalue is two
• Three-connected graphs whose maximum nullity is at most three
• Vertex version of the Wiener theorem
• Wiener index of trees: Theory and applications

Cited in

(37)

• Infinite family of transmission irregular trees of even order
• Graphs whose Wiener index does not change when a specific vertex is removed
• Infinite family of 3-connected cubic transmission irregular graphs
• -distance-balanced graphs
• A relation between \(D\)-index and Wiener index for \(r\)-regular graphs
• On graphs whose Wiener complexity equals their order and on Wiener index of asymmetric graphs
• Infinite family of 2-connected transmission irregular graphs
• Metric properties of generalized Sierpiński graphs over stars
• k-paths of k-trees
• On the status sequences of trees
• On quartic transmission irregular graphs
• Transmission in H-naphtalenic nanosheet
• General transmission lemma and Wiener complexity of triangular grids
• A construction of distance cospectral graphs
• Distance and eccentric sequences to bound the Wiener index, Hosoya polynomial and the average eccentricity in the strong products of graphs
• scientific article; zbMATH DE number 168165 (Why is no real title available?)
• On 2-distance-balanced graphs
• On the largest distance (signless Laplacian) eigenvalue of non-transmission-regular graphs
• Brouwer type conjecture for the eigenvalues of distance signless Laplacian matrix of a graph
• On 2-connected transmission irregular graphs
• Constructions of cospectral graphs with different zero forcing numbers
• scientific article; zbMATH DE number 7546725 (Why is no real title available?)
• How to count k-paths
• scientific article; zbMATH DE number 7415568 (Why is no real title available?)
• On the smallest eigenvalue of D_α-matrix of connected graphs
• Generalized transmission neighbor indices: graph connectivity analysis and its chemical relevance
• On distance-balanced generalized Petersen graphs
• A new characterization of \(k\)-trees and some applications
• Spectra of variants of distance matrices of graphs and digraphs: a survey
• Relation between generalized distance spread and some topological indices
• On 2-distance-balancedness of vertex transitive generalized Petersen graphs
• An efficient algorithm for generating transmission irregular trees
• On the main distance-based entropies: the eccentricity- and Wiener-entropy
• The conjecture on distance-balancedness of generalized Petersen graphs holds when internal edges have jumps 3 or 4
• Bounds on the closeness centrality of a graph
• On \(\{1,2\}\)-distance-balancedness of generalized Petersen graphs
• Constructing adjacency and distance cospectral graphs via regular rational orthogonal matrix

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: On the Wiener index, distance cospectrality and transmission-regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2399284)