Characterizing graphs with fully positive semidefinite Q-matrices

DOI10.1016/J.LAA.2023.04.018zbMATH Open1515.05119arXiv2208.11002OpenAlexW4366607396MaRDI QIDQ6155673FDOQ6155673

Authors: Hajime Tanaka 

Publication date: 5 June 2023

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

Abstract: For $qinmathbbR$, the $Q$-matrix $Q=Q_q$ of a connected simple graph $G=(V,E)$ is $Q_q=(q^{partial(x,y)}{)}_{x,yinV}$, where $partial$ denotes the path-length distance. Describing the set $pi(G)$ consisting of those $qinmathbbR$ for which $Q_q$ is positive semidefinite is fundamental in asymptotic spectral analysis of graphs from the viewpoint of quantum probability theory. Assume that $G$ has at least two vertices. Then $pi(G)$ is easily seen to be a nonempty closed subset of the interval $[-1,1]$. In this note, we show that $pi(G)=[-1,1]$ if and only if $G$ is isometrically embeddable into a hypercube (infinite-dimensional if $G$ is infinite) if and only if $G$ is bipartite and does not possess certain five-vertex configurations, an example of which is an induced $K_{2,3}$.

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

Recommendations

• Positive Q-matrices of graphs
• Distance matrices and quadratic embedding of graphs
• The \(Q\)-matrix completion problem
• The positive \(Q\)-matrix completion problem
• scientific article; zbMATH DE number 5850549

zbMATH Keywords

positive definite kernel\(Q\)-matrix

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12) Positive definite functions on groups, semigroups, etc. (43A35)

Cites Work

• Title not available (Why is that?)
• Distance-regular graphs the distance matrix of which has only one positive eigenvalue
• Title not available (Why is that?)
• Distance regular subgraphs of a cube
• An algebraic approach to association schemes
• Distance-preserving subgraphs of hypercubes
• Distance-regular graphs
• Quantum probability and spectral analysis of graphs. With a foreword by Professor Luigi Accardi.
• An introduction to the theory of reproducing kernel Hilbert spaces
• Positivity of Gibbs states on distance-regular graphs
• Positive-definite kernels, length functions on groups and a noncommutative von Neumann inequality
• Distance matrices and quadratic embedding of graphs
• Scaling limits for the Gibbs states on distance-regular graphs with classical parameters
• Asymptotic spectral analysis of growing regular graphs
• Title not available (Why is that?)
• Markov product of positive definite kernels and applications to Q-matrices of graph products
• Positive Q-matrices of graphs

Cited In (5)

• On the maximum positive semi-definite nullity and the cycle matroid of graphs
• Positive semidefiniteness of \(A_\alpha (G)\) on some families of graphs
• Characterization of completely positive graphs
• Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without \(K_{5}\) minors
• Positive Q-matrices of graphs

This page was built for publication: Characterizing graphs with fully positive semidefinite \(Q\)-matrices

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