Graph functions maximized on a path

DOI10.1016/J.LAA.2015.07.012MaRDI QIDQ745175zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 13 October 2015

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

distance matrixlargest eigenvaluepathdistance Laplaciandistance signless Laplacian

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inequalities involving eigenvalues and eigenvectors (15A42) Distance in graphs (05C12) Connectivity (05C40)

Abstract: Given a connected graph $G$of order $n$ and a nonnegative symmetric matrix $A=left[a_{i,j}ight]$ of order $n,$ define the function $F_{A}left(Gight)$ as% [ F_{A}left( G ight) =sum_{1leq i<jleq n}d_{G}left( i,j ight) a_{i,j}, ] where $d_{G}left(i,jight)$ denotes the distance between the vertices $i$ and $j$ in $G.$ In this note it is shown that $F_{A}left(Gight)leq{F}_{A}left(Pight),$for some path of order $n.$ Moreover, if each row of $A$ has at most one zero off-diagonal entry, then $F_{A}left(Gight)<F_{A}left(Pight),$for some path of order $n,$ unless $G$ itself is a path. In particular, this result implies two conjectures of Aouchiche and Hansen: - the spectral radius of the distance Laplacian of a connected graph $G$ of order $n$ is maximal if and only if $G$ is a path; - the spectral radius of the distance signless Laplacian of a connected graph $G$ of order $n$ is maximal if and only if $G$ is a path.

Recommendations

• The distance spectrum of the pathP_nand The First Distance Eigenvector of Connected Graphs
• Convex and quasiconvex functions on trees and their applications
• A proof of a conjecture on the distance spectral radius and maximum transmission of graphs
• On the distance and distance Laplacian eigenvalues of graphs
• On the sum of k largest distance eigenvalues of graphs

Cites work

• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Bounds on the distance signless Laplacian spectral radius in terms of clique number
• Distance spectral radius of trees with fixed maximum degree
• On the distance Laplacian spectra of graphs
• On the distance signless Laplacian spectral radius of graphs
• On the eigenvalues of trees
• Properties of spectra of graphs and line graphs
• Some properties of the distance Laplacian eigenvalues of a graph.
• The distance spectrum of the pathP_nand The First Distance Eigenvector of Connected Graphs
• The path is the tree with smallest greatest Laplacian eigenvalue
• Two Laplacians for the distance matrix of a graph

Cited in

(12)

• Remoteness and distance, distance (signless) Laplacian eigenvalues of a graph
• Distance (signless) Laplacian spectral radius of uniform hypergraphs
• On the first two largest distance Laplacian eigenvalues of unicyclic graphs
• On the distance Laplacian spectral radius of bicyclic graphs
• The changes in distance Laplacian spectral radius of graphs resulting from graft transformations
• Extremal results on distance Laplacian spectral radius of graphs
• On the multiplicity of distance signless Laplacian eigenvalues of graphs
• On the \(D_\alpha\)-spectra of graphs
• Path-value functions for which Dijkstra's algorithm returns optimal mapping
• Spectra of variants of distance matrices of graphs and digraphs: a survey
• Convex and quasiconvex functions on trees and their applications
• The generalized distance matrix

This page was built for publication: Graph functions maximized on a path

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