Quadratic embedding constants of graphs: bounds and distance spectra

DOI10.1016/J.LAA.2023.09.024MaRDI QIDQ6087863zbMATH OpenFDO

Authors Projesh Nath Choudhury, Raju Nandi

Publication date 16 November 2023

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

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

zbMATH Keywords

cluster of graphsdistance matrixdistance spectra of graphsdouble starEuclidean distance geometryquadratic embedding constanttree

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph operations (line graphs, products, etc.) (05C76)

Abstract: The quadratic embedding constant (QEC) of a finite, simple, connected graph $G$ is the maximum of the quadratic form of the distance matrix of $G$ on the subset of the unit sphere orthogonal to the all-ones vector. The study of these QECs was motivated by the classical work of Schoenberg on quadratic embedding of metric spaces [Ann. of Math., 1935] and [Trans. Amer. Math. Soc., 1938]. In this article, we provide sharp upper and lower bounds for the QEC of trees. We next explore the relation between distance spectra and quadratic embedding constants of graphs - and show two further results: $(i)$ We show that the quadratic embedding constant of a graph is zero if and only if its second largest distance eigenvalue is zero. $(ii)$ We identify a new subclass of nonsingular graphs whose QEC is the second largest distance eigenvalue. Finally, we show that the QEC of the cluster of an arbitrary graph $G$ with either a complete or star graph can be computed in terms of the QEC of $G$. As an application of this result, we provide new families of examples of graphs of QE class.

Recommendations

• Distance matrices and quadratic embedding of graphs
• On quadratic embedding constants of star product graphs
• Determining finite connected graphs along the quadratic embedding constants of paths
• Quadratic embedding constants of graph joins
• Quadratic embedding constants of wheel graphs

Cites work

• An example of a non nuclear C*-algebra, which has the metric approximation property
• Determining finite connected graphs along the quadratic embedding constants of paths
• Distance matrices and quadratic embedding of graphs
• scientific article; zbMATH DE number 4081841 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• Kirchhoff index of composite graphs
• Markov product of positive definite kernels and applications to Q-matrices of graph products
• On Isometric Embeddings of Graphs
• On quadratic embedding constants of star product graphs
• On the Addressing Problem for Loop Switching
• Positive Q-matrices of graphs
• Positive-definite kernels, length functions on groups and a noncommutative von Neumann inequality
• Quadratic embedding constants of graph joins
• Quadratic embedding constants of path graphs
• Quantum probability and spectral analysis of graphs. With a foreword by Professor Luigi Accardi.
• Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert

Cited in

(5)

• On quadratic embeddability of bipartite graphs and theta graphs
• A classification of graphs through quadratic embedding constants and clique graph insights
• Quadratic embedding constants of fan graphs and graph joins
• Quadratic embedding constants of corona graphs
• Quadratic embedding constants of lexicographic product graphs

This page was built for publication: Quadratic embedding constants of graphs: bounds and distance spectra

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