TY - JOUR
T1 - Distance matrices and quadratic embedding of graphs
AU - Obata, Nobuaki
AU - Zakiyyah, Alfi Y.
N1 - Funding Information:
NO is supported by JSPS KAKENHI 16H03939 and by JSPS Open Partnership Joint Research Project “Extremal graph theory, algebraic graph theory and mathematical approach to network science” (2017–18). AYZ is grateful for kind hospitality at the Graduate School of Information Sciences, Tohoku University and for the support by the Ministry of Research, Technology and Higher Education of the Republic of Indonesia through Sandwich-Like Program.
Publisher Copyright:
© 2018 Indonesian Combinatorics Society.
PY - 2018
Y1 - 2018
N2 - A connected graph is said to be of QE class if it admits a quadratic embedding in a Hilbert space, or equivalently, if the distance matrix is conditionally negative definite. Several criteria for a graph to be of QE class are derived from the point of view of graph operations. For a quantitative criterion the QE constant is introduced and concrete examples are shown with explicit calculation. If the distance matrix admits a constant row sum, the QE constant coincides with the second largest eigenvalue of the distance matrix. The QE constants are determined for all graphs on n vertices with n ≤ 5, among which two are not of QE class.
AB - A connected graph is said to be of QE class if it admits a quadratic embedding in a Hilbert space, or equivalently, if the distance matrix is conditionally negative definite. Several criteria for a graph to be of QE class are derived from the point of view of graph operations. For a quantitative criterion the QE constant is introduced and concrete examples are shown with explicit calculation. If the distance matrix admits a constant row sum, the QE constant coincides with the second largest eigenvalue of the distance matrix. The QE constants are determined for all graphs on n vertices with n ≤ 5, among which two are not of QE class.
KW - Conditionally negative definite matrix
KW - Distance matrix
KW - Euclidean distance matrix quadratic embedding
KW - QE constant
UR - http://www.scopus.com/inward/record.url?scp=85045024522&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85045024522&partnerID=8YFLogxK
U2 - 10.5614/ejgta.2018.6.1.4
DO - 10.5614/ejgta.2018.6.1.4
M3 - Article
AN - SCOPUS:85045024522
SN - 2338-2287
VL - 6
SP - 37
EP - 60
JO - Electronic Journal of Graph Theory and Applications
JF - Electronic Journal of Graph Theory and Applications
IS - 1
ER -