Determining finite connected graphs along the quadratic embedding constants of paths

Edy Tri Baskoro, Nobuaki Obata

Abstract


The QE constant of a finite connected graph G, denoted by QEC(G), is by definition the maximum of the quadratic function associated to the distance matrix on a certain sphere of codimension two. We prove that the QE constants of paths Pn form a strictly increasing sequence converging to −1/2. Then we formulate the problem of determining all the graphs G satisfying QEC(Pn)≤QEC(G)<QEC(Pn + 1). The answer is given for n = 2 and n = 3 by exploiting forbidden subgraphs for QEC(G)< − 1/2 and the explicit QE constants of star products of the complete graphs.


Keywords


conditionally negative definite matrix; claw-free graphs; distance matrix; quadratic embedding constant; star product graph

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.23

References

G. Aalipour, A. Aida, Z. Berikkyzy, J. Cummings, and J. De Silva, On the distance spectra of graphs, Linear Algebra Appl. 497 (2016), 66–87.

M. Aouchiche and P. Hansen, Distance spectra of graphs: a survey, Linear Algebra Appl. 458 (2014), 301–386.

R. Balaji and R.B. Bapat, On Euclidean distance matrices, Linear Algebra Appl. 424 (2007), 108–117.

M. Bozejko, T. Januszkiewicz and R.J. Spatzier, Infinite Coxeter groups do not have Kazhdan’s property, J. Operator Theory 19 (1988), 63–67.

M. Bozejko, Positive-definite kernels, length functions on groups and noncommutative von Neumann inequality, Studia Math. 95 (1989), 107–118.

M.M. Deza and M. Laurent, Geometry of Cuts and Metrics, Springer-Verlag, Berlin, 1997.

R. Faudree, E. Flandrin, and Z. Ryjacek, Claw-free graphs – A survey, Discrete Math. 164 (1997), 87–147.

U. Haagerup, An example of a nonnuclear C∗-algebra which has the metric approximation property, Invent. Math. 50 (1979), 279–293.

G. Indulal and I. Gutman, On the distance spectra of some graphs, Mathematical Communications 13 (2008), 123–131.

G. Jaklic and J. Modic, On Euclidean distance matrices of graphs, ˇ Electron. J. Linear Algebra 26 (2013), 574–589.

G. Jaklic and J. Modic, Euclidean graph distance matrices of generalizations of the star graph, Appl. Math. Comput. 230 (2014), 650–663.

J.H. Koolen and S.V. Shpectorov, Distance-regular graphs the distance matrix of which has only one positive eigenvalue, European J. Combin. 15 (1994), 269–275.

L. Liberti, G. Lavor, N. Maculan, and A. Mucherino, Euclidean distance geometry and applications, SIAM Rev. 56 (2014), 3–69.

W. Młotkowski and N. Obata, On quadratic embedding constants of star product graphs, Hokkaido Math. J. 49 (2020), 129–163.

N. Obata, Positive Q-matrices of graphs, Studia Math. 179 (2007), 81–97.

N. Obata, Markov product of positive definite kernels and applications to Q-matrices of graph products, Colloq. Math. 122 (2011), 177–184.

N. Obata, Quadratic embedding constants of wheel graphs, Interdiscip. Inform. Sci. 23 (2017), 171–174.

N. Obata and A.Y. Zakiyyah, Distance matrices and quadratic embedding of graphs, Electron. J. Graph Theory Appl. 6 (1) (2018), 37–60.

I.J. Schoenberg, Remarks to Maurice Frechet’s article ”Sur la d ´ efinition axiomatique d’une classe d’espace distancis vectoriellement applicable sur l’espace de Hilbert”, Ann. Math. 36 (1935), 724–732.

I.J. Schoenberg, Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44n(1938), 522–536.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats