/^creative ^commor ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 9 (2015) 151-163 On minimal forbidden subgraphs for the class of EDM-graphs Gasper Jaklic FMF and IMFM, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia and IAM, University ofPrimorska, Slovenia Jolanda Modic * XLAB d.o.o., Pot za Brdom 100, 1000 Ljubljana, Slovenia and FMF, University of Ljubljana, Slovenia Received 2 April 2013, accepted 2 April 2014, published online 21 November 2014 Abstract In this paper, a relation between graph distance matrices and Euclidean distance matrices (EDM) is considered. Graphs, for which the distance matrix is not an EDM (NEDM-graphs), are studied. All simple connected non-isomorphic graphs on n < 8 nodes are analysed and a characterization of the smallest NEDM-graphs, i.e., the minimal forbidden subgraphs, is given. It is proven that bipartite graphs and some subdivisions of the smallest NEDM-graphs are NEDM-graphs, too. Keywords: Graph, Euclidean distance matrix, distance, eigenvalue. Math. Subj. Class.: 15A18, 05C50, 05C12 1 Introduction A matrix D e Rnxn is Euclidean distance matrix (EDM), if there exist x\, X2,..., xn € Rr, such that dj = ||xj - Xj ||2, i,j = 1,2 ,...,n. The minimal possible r is called the embedding dimension (see [2], e.g.). * Corresponding author. This research was funded in part by the European Union, European Social Fund, Operational Programme for Human Resources, Development for the Period 2007-2013. The author would like to thank XLAB d.o.o., Dr. Daniel Vladusic and Dr. Gregor Berginc for all the support. E-mail addresses: gasper.jaklic@fmf.uni-lj.si (Gasper Jaklic), jolanda.modic@gmail.com (Jolanda Modic) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 152 Ars Math. Contemp. 9 (2015) 151-163 Euclidean distance matrices were introduced by Menger in 1928 and have received a considerable attention. They were studied by Schoenberg [13], Young and Householder [14], Gower [4], and many other authors. In recent years many new results were obtained (see [5, 7, 8, 11] and the references therein). They are used in various applications in linear algebra, graph theory, geodesy, bioinfor-matics, chemistry, e.g., where frequently a question arises, what can be said about a set of points, if only interpoint distance information is known. Some examples can be found in [2]. EDMs have many interesting properties. They are symmetric, hollow (i.e., with only zeros on the diagonal) and nonnegative. The sum of their eigenvalues is zero and they have exactly one positive eigenvalue (for a nonzero matrix). Schoenberg ([13]), Hayden, Reams and Wells ([5]) gave the following characterization of EDMs. Theorem 1.1. Let D e Rnxn be a nonzero symmetric hollow matrix and let e e Rn be the vector of ones. The following propositions are equivalent: (a) The matrix D is EDM. (b) For all x e Rn such that xT e = 0, xTDx < 0. (c) The matrix D has exactly one positive eigenvalue and there exists w e Rn such that Dw = e (1.1) and wTe > 0. Throughout the paper we will use the notation e for the vector of ones of appropriate size. Vectors e4 will denote the standard basis. Let G be a graph with a vertex set V(G) and an edge set E(G). Let the distance d(u, v) between vertices u,v e V(G) be defined as their graph distance, i.e., the length of the shortest path between them. Let G := [d(u, v)]„,vey(G) be the distance matrix of G. If the graph distance matrix of a graph is EDM, the graph is called an EDM-graph. Otherwise the graph is a NEDM-graph. Graph distance matrices of EDM-graphs were studied in several papers. Path and cycles were analysed in [9]. Star graphs and their generalizations were considered in [6, 10]. Some results on Cartesian products of EDM-graphs are also known (see [11]). However, the characterization of EDM-graphs in general is still an open problem. In this paper, all simple connected non-isomorphic graphs on n < 8 nodes are analysed and a characterization of the smallest NEDM-graphs, i.e., the minimal forbidden subgraphs, is given. In algebraic graph theory, a lot is known on the adjacency matrix and the Laplacian matrix of a graph. Many results on their eigenvalues exist, but not much is known on the graph distance matrix. Hopefully, this paper will provide a deeper insight into the relation between general graphs or networks and EDM theory. There are some interesting possibilities of application. Molecular conformation in bioinformatics, dimensionality reduction in statistics, 3D reconstruction in computer vision, just to name a few. The structure of the paper is as follows. In Section 2, all NEDM-graphs on n < 8 nodes are considered. Analysis of their properties enables us to find some larger NEDM-graphs, which are presented in sections 3 and 4. A proof that bipartite graphs are NEDM-graphs G. Jaklic and J. Modic: On minimal forbidden subgraphs for the class of EDM-graphs 153 is given. We present two families of subdivision graphs of the smallest NEDM-graphs that are NEDM-graphs, too. There exist graphs, for which the system (1.1) has no solution. Such graphs are studied in Section 5. The paper is concluded with an example, where we show that not all subdivisions of graphs result in NEDM-graphs. 2 The smallest NEDM-graphs In this section we consider simple connected non-isomorphic graphs on n < 5 nodes and find the smallest NEDM-graphs. There is one simple connected graph on 2 nodes, the path graph P2, and there exist only two simple connected graphs on 3 nodes, the path graph P3 and the cycle graph C3. In [9] it was proven that path graphs and cycle graphs are EDM-graphs. For n = 4, there are 6 simple connected graphs (see Fig. 1). First four of them are the star graph S4, the path graph P4, the cycle graph C4 and the complete graph K4, respectively, which are EDM-graphs (see [9, 10]). Therefore we only need to consider the last two graphs, g45) and g46). Figure 1: Simple connected graphs on 4 nodes. Let us denote vertices of graphs £45) and £46) counterclockwise by 1,2, 3 and 4 starting with the upper right vertex. The characteristic polynomials of the corresponding graph distance matrices G (5) 0 1 2 2 0 1 2 1 1 0 1 1 and G46) = 1 0 1 1 2 1 0 1 2 1 0 1 2 1 1 0 1 1 1 0 are 5) (A) = (A + 1)(A3 - A2 - 11A - 7), pG(6) (A) = (A + 1)(A + 2)(A2 - 3A - 2). Thus matrices g45) and g46) have eigenvalues 0, i = 5, 6, by Theorem 1.1 graphs G(5) and G(6) are EDM-graphs. Thus there are no NEDM-graphs on 4 nodes. In the case n = 5, there are 21 simple connected graphs (see Fig. 2). V J 13 20 21 Figure 2: Simple connected graphs on 5 nodes. Graphs G^, i < 5, are the path graph P5, the cycle graph C5, the complete graph K5, the star graph S5 and the tree 75, respectively. Since they are EDM-graphs (see [1]), we (i) only need to analyse graphs G5 , i = 6,7,..., 21. A straightforward calculation shows that the graph distance matrix G^ of the graph G (i) 6,7,..., 19, has exactly one positive eigenvalue and that there exists w g : such that G<5')wr(i) = e and wT e > 0. By Theorem 1.1, graphs g56), g5?), . g519) are EDM-graphs. We are left with graphs g520) and g521) (see Fig. 3). The characteristic polynomials of the corresponding graph distance matrices G(20) = 0 2 2 1 1 0 2 2 1 1 to 0 2 1 1 and G521) = 2 0 1 1 1 to 2 0 1 1 2 1 0 1 1 1 1 1 0 2 1 1 1 0 2 1 1 1 2 0 1 1 1 2 0 are pG(20) (A) = -(A + 2)3(A2 - 6A + 2), g5 PG(21) (A) = -(A + 1)(A + 2)(A3 - 3A2 - 12A + 2). 4 G. Jaklic and J. Modic: On minimal forbidden subgraphs for the class of EDM-graphs 155 20 Figure 3: The graphs g520) and g521). Thus matrices g520) and G|521) have spectra an(20) = {3 + V7, 3 -V7, -2, -2, -2} and an(21) = {5.2, 0.2,-1, -2, -2.4} . (21) Exact eigenvalues for G5 ) can be calculated by using Cardano's formula. Here they were calculated numerically. Since matrices g5,20) and g5,21) have two positive eigenvalues, graphs G520) and G^21) are NEDM-graphs. These are the smallest NEDM-graphs. An induced subgraph H of a graph G is a subset of the vertices V(G) together with all edges whose endpoints are both in this subset. Proposition 2.1. Let G be a simple connected graph and let H be its induced subgraph. If H is a NEDM-graph, the graph G is a NEDM-graph as well. Proof. Let n and m < n, denote the number of nodes in graphs G and H, respectively. Let us order vertices of the graph G in such a way that the first m vertices are the vertices of the graph H. Thus the distance matrix G of the graph G is of the form G H * where H is the distance matrix of the graph H. Every principal submatrix of an EDM has to be an EDM as well. Thus since H is not an EDM, neither is G. Therefore G is a NEDM-graph. □ All NEDM-graphs form a set of forbidden subgraphs of the class of EDM-graphs. Graphs g520) and G^21) are the minimal forbidden subgraphs. All minimal forbidden subgraphs on 6 and 7 nodes can be seen in Fig. 4 and Fig. 5. Figure 4: NEDM-graphs for n = 6. Let m(n) be the number of NEDM-graphs on n nodes and let mnew(n) be the number of NEDM-graphs on n nodes for which none of the induced subgraphs is NEDM-graph. 156 Ars Math. Contemp. 9 (2015) 151-163 10 Figure 5: NEDM-graphs for n = 7. We denote the number of non-isomorphic simple connected graphs on n nodes by g(n). Table 1 shows how numbers m(n) and mnew (n) grow with n. The calculations were done in the following way. By using program geng in Nauty ([12]) we generated all simple connected non-isomorphic graphs on n < 8 nodes. Then we applied Theorem 1.1 to determine whether a graph is an EDM-graph. Computations were done in Mathematica. n g(n) m(n) mnew (n) 5 21 2 2 6 112 27 3 7 853 341 13 8 11117 7946 48 Table 1: Number of NEDM-graphs compared to the number of all graphs on n nodes. 3 Bipartite graphs A quick observation shows that the graph g520) is bipartite (see Fig. 3). Let Guk,zn-k be a simple connected bipartite graph on n > 5 nodes, whose vertices are divided into two disjoint sets Uk = {u^ u2,..., uk}, Zn-k = {uk+1, uk+2,..., un}, k = 2,3,..., n - 2, such that every edge connects a vertex in Uk to a vertex in Zn-k (see Fig. 6). The sets Uk and Zn-k are called the partition sets. A graph join G1 + G2 of graphs G1 and G2 with disjoint vertex sets V(G1), V(G2) and edge sets E (G1), E (G2) is the graph with the vertex set V (G1) U V (G2) and the edge set E(G1) UE(G2) U {(u,v); u e V(G1), v e V(G2)}. It is the graph union G1 U G2 with all the edges that connect the vertices of the first graph with the vertices of the second graph. The graph G Uk ,zn-k can also be written as the graph join of two empty graphs on k and n - k vertices, i.e., GUk,zn-k = Ok + On-k. The corresponding graph distance matrix is Gk.n—k 2(Ek,k — Ik ) Ek En-k,k 2(En-k,n-k In-k) € Rn G. Jaklic and J. Modic: On minimal forbidden subgraphs for the class of EDM-graphs 157 where Ep,q e Rpxq and Ip e Rpxp are the matrix of ones and the identity matrix, respectively. Uk U 3 U 2 Ul Un Uk 2 Uk l Figure 6: The graph Guk,zn Theorem 3.1. A simple connected bipartite graph Guk,zn-k on n > 5 nodes and with partition sets Uk and Zn-k is a NEDM-graph. Proof. Since graphs Guk,zn-k and Gun-k,zk are isomorphic, it is enough to see that the theorem holds true for k = 2, 3,..., |_n/2j. Let us analyse the eigenvalues of the graph distance matrix of G uk,zn-k. A simple computation shows that u1,i = [ef - ef, 0T]T solves the equation Gfc,n-fcu1,i = -2u1)i for all i = 2, 3,..., k, and that u2,j = [0T, eT - ef ]T, solves the equation Gk,n-ku2,j = -2u2j for all j = 2,3,..., n - k. Therefore Gfcjn-fc has an eigenvalue -2 with multiplicity n - 2. Now let us take u = [a eT, eT]T. The relation Gk,n-ku = Au yields the system of equations 2(k - 1)a + n - k = Aa, ka + 2(n - k - 1) = A, which has solutions 2k - n ± V(n - 2k)2 + k(n - k) ai,2 =-k-, Ai,2 = n - 2 ± V(n - 2k)2 + k(n - k). Relations n > 5 and 2 < k < |_n/2j imply that «i,2 and A12 are well-defined. Since Ai > 0 and A1 • A2 = 3(k - 2)(n - 2 - k) + 2(n - 4) > 0, we conclude that A2 > 0. Thus, by Theorem 1.1, the graph Guk,zn-k is a NEDM-graph. ' " □ Remark 3.2. For k = 1, the graph Guk,Zn-k is the star graph Sn, which is an EDM-graph. 158 Ars Math. Contemp. 9 (2015) 151-163 4 Graph subdivision Let G be a graph. A subdivision of an edge in G is a substitution of the edge by a path. For example, an edge of the cycle Cn can be subdivided into three edges, resulting in the cycle graph Cn+2. Recall the NEDM-graph g520). It contains a 4-cycle c connecting nodes 2, 3, 4 and 5 (see Fig. 7). We can construct larger NEDM-graphs by performing a subdivision of the cycle c. Let G^ be a graph on n nodes, obtained by subdividing the cycle c in the graph G520) as seen in Fig. 7. Such graphs are G^ Fig. 5). ' G^ and G5270) g74) (see Fig. 4 and 20 5,n Figure 7: Construction of graphs G5 (20) Let ei denote the standard basis and let Cn be the graph distance matrix of the cycle graph Cn (see [9]). The matrix Cn is a circulant matrix (see [3]), generated by its first row: n — 1 n — 1 n — 3 0, 1, ...,-, -, -,..., 1, n odd, '' 2 2 2 n — 2 n n — 2 0, 1, ...,-, —, -,..., 1, n even. ' ' ' 2 ' 2' 2 ' ' ' We will use the notation for the (i, j)-th element of the matrix Cn. The structure of the matrix Cn implies C^2) = C^ = 1, C^ = 2, n > 4, (4.1) and ( L(n — 1)/2j, i =1, C^,L(n+4)/2J) = J [n/2j, i = 2, n > 3. ( L(n — 2)/2j, i = 3, Theorem 4.1. Graphs G5V, n > 5, are NEDM-graphs. Proof. The graph distance matrix of the graph g52^°), n > 5, is (4.2) G(20) = G5,n = 0 (Cn-1 + 2/)e2 eT (Cn-1 +2/)' Cn 1 By Theorem 1.1 it is enough to show that there exists x G Rn, such that xTe = 0 and xTG52n)x > 0. G. Jaklic and J. Modic: On minimal forbidden subgraphs for the class of EDM-graphs 159 Let us take x = [-yTe, yT]T, with nr(-ei + e2 - e^ + e(n+3)/2, n odd, nr(-ei + (e2 - e3^ + e(n+2)/2, n even. We will show that xTG^x = yTCn-iy - 2(yTe) (eTCn-iy + 2(yTe2)) > 0. (4.3) From f ^, n odd, f s-1, n odd, yTe = I , n even, ** ^* = \ , n even, it follows that _ (20) _ . (n - 3)(eTCn-iy + n - ^ , n odd, xTx = y Cn-iy +< 2, , L ^ (4.4) T5'" y n-iy '' n!-M(eTC„-iy + , neven. Firstly, let n be odd. Terms in the relation (4.4) simplify to yTC y = (n - 1)2 (C(i,2) C(i,3) + C(2,3)\ y Cn-iy =--2- ^°n-i - Cn-i + Cn-iJ - - (n - 1) (C(i.(n+3)/2) - C(2,(n+3)/2) + C(3,(n+3)/2) ^ eTC y = C(2,(n+3)/2) n - 1 (C(i,2) + C( e2 Cn-iy = Cn-i --(^n-i + Cn By (4.1) and (4.2), yTC„-iy = - —-——, e'T C„-iy = and .Tr< (n - 1)(n - 5) ^^ n - 1 '* Cn-iy =--^-, e2 Cn-iy =--, T s-y (20) x G5,nx = n - 1, which satisfies the requirement (4.3) for all n > 5. When n is even, the terms in the relation (4.4) simplify to yTCn-iy = - (n - ffi - 1) ((n - 2)(ncni-2i) - n^ + (n - DC^V + 2nCn-(in+2)/2) - 2(n - 1) - Cn-(r+2)/2))j , eTC y = n - 1 C(2,(n+2)/2) n - 2 (C(i,2) + n - 1 C(2,3)\ e2 Cn-iy = —Cn-i - — \Cn- + ) ' By (4.1) and (4.2), yTC y (n - 1)2(n - 2)(n - 4) eTC y n - 2 y Cn-iy =--2n-, eT Cn-iy = — 160 Ars Math. Contemp. 9 (2015) 151-163 and xT G(20)x _ n - 2 which satisfies the requirement (4.3) for all n > 5. □ (21) Similarly, we can subdivide cycles of the graph £5 and produce NEDM-graphs (see Fig. 8). The graph g521) contains a 3-cycle c connecting nodes 3, 4 and 5. Let be a graph on n nodes, obtained by subdividing the cycle c in the graph g521) as seen in Fig. 8. Such graphs are ^ _ g521), ^ _ £<(3) and g5271) _ &(6) (see Fig. 4 and Fig. 5). 21 5,n Figure 8: Graphs G^. Theorem 4.2. Graphs gf!, n > 5, are NEDM-graphs. Proof. The graph distance matrix of the graph g52^), n > 5, is "0 1 T UT G(21) _ G5,n _ 1 0 T U V Cn—2 where 1 + (-1)n U _ (Cn-2 + I>2 + e - y----e(n+2)/2' V _ (C„-2 + I)e2 + y, and y _ J2i(=2+1)/2 ek. Analogous to the proof of Theorem 4.1, we can show that for x _ a [a, -a, zT] , where 2 n—3 2 ' n odd, n even, and z n—1 e1 - n—3e2 - e(n+1)/2, n odd, n_2 n_4 e1 - 4e2 - e(„+2)/2, n even, the expression xTG^x _ zTCn—2z + 2a (uTz - vTz - a) is positive. Relations Cn—2 _ 1, C(1,(n+1)/2) _ C(2,(n+1)/2) n — 3 C (1,(n+2)/2) n— 2 n - 4 2 , C n—2 n—2 (2,(n+2)/2) _ n - 2 n— 2 a G. Jaklic and J. Modic: On minimal forbidden subgraphs for the class of EDM-graphs 161 imply and T u z which yields 2, n odd, 1, n even, Z Cn-2Z = T v z 3 — n, n odd, 4 — n, n even, (n-3)(n+1) ,, --2 + ), n odd, (n-2)(n-4) 2 , n even, 2, n odd, □ Thus by Theorem 1.1, the matrix G^ is a NEDM. 5 Systems with no solution When verifying whether a graph G with the corresponding graph distance matrix G is an EDM-graph, by Theorem 1.1 one can check if there exists a solution of the equation Gw = e, such that wT e > 0. For n > 7 there exist graphs, for which the equation Gw = e has no solution. Let Gk,n-k be the graph join of a complete graph Kk and an empty graph On-k, n > 7, k = 2, 3,..., n — 3, i.e., Gk,n-k = Kk + On-k. The graph Kk contains vertices 1,2,..., k and the graph On-k contains vertices k +1, k + , n. Thus the corresponding graph distance matrix is 2 Gk2n k Ek,k — Ik k2n - k En — k,k 2(En-k,n-k J-n-k) For n = 7 and k = 3 the equation G3 4 w = e has no solution since the ranks of the matrix G3,4 and its augmented matrix [G3,4|e] are different, rank(G3,4) = 6 and rank([G3 4|e]) = 7. The same holds true if n = 7 and k = 4. Thus by Theorem 1.1 matrices G3 4 and G4 3 are not EDMs. On the other hand, for n = 8 the equation Gk,8-k w = e has a solution for all k G {3,4,5}. In general, the matrix Gk,n-k is a NEDM. Theorem 5.1. The graph Kk + On-k, n > 7, k = 2,3,..., n — 3, is a NEDM-graph. Proof. Let Gk,n-k be the graph distance matrix of the graph Kk + On-k, n > 7, k = 2, 3, . . . , n - 3. For k = 2 we take 1 2 1 T w = -[4 — n, 4 — n, 1,1,..., 1] . We can verify that G2,n-2w = e and wTe = (6 — n)/2 < 0. Thus by Theorem 1.1 the matrix G2,n-2 is a NEDM. Now let k = 3, 4, . . . , n - 3. For n = 7 the proof has already been done above. For n > 8 let u = [a eT, eT]T, where vectors e are of sizes k and n — k, respectively. The relation Gk,n-ku = Au yields the system of equations a(k — 1) + n — k = Aa, ak + 2(n — k — 1) = A, 2, n even. 162 Ars Math. Contemp. 9 (2015) 151-163 with solutions ai,2 = 2k (3k - 2n +1 ± ^4(n - k)(n - k - 1) + (k + l}2) Aij2 = 1 (2n - k - 3 ± ^4(n - k)(n - k - 1) + (k + l)2) . Relations n > 8 and 3 < k < n - 3 imply that and Ai,2 are well-defined. Since Ai > 0 and A1 • A2 = (n - 3 - k)(k - 3) + n - 7 > 0, we conclude that A2 > 0. Thus, by Theorem 1.1, graph + On-k is aNEDM-graph. □ Remark 5.2. For k = 1 and k = n - 1, the graphs + On-k are the star graph Sn and the complete graph Kn, respectively, which are EDM-graphs. Remark 5.3. For k = n - 2, the graph Kn-2 + O2 is an EDM-graph. The graph distance matrix Gn-2,2 has eigenpairs (-2, [0T, eT - eT ]T) , (-1, [ef - eT, 0T ]T) , i = 2, 3,...,n - 2, and with (Ai,2, [ai,2 eT, eT ai,2 n - 5 ± Vn2 - 2n + 9 2(n - 2) and A12 - 1 ± vn2 - 2n + 9 The eigenvalue A1 is obviously positive. From A1 • A2 = -2 it follows that A2 < 0. One can easily verify that w = (1/2) [0T, eT] solves the equation Gn-2,2w = e. Since wTe = 1, Theorem 1.1 implies that Gn-2,2 is EDM. 6 Conclusion In Section 4 we studied subdivisions of graphs. Not all graph subdivisions result in NEDM- graphs. Consider subdividing graph £5 sponding graph distance matrix (20) as in Fig. 9 and denoting it by H. The corre- 0 1 2 2 3 2 1 10 12 2 12 2 10 12 2 2 H = 2 2 10 12 1 3221012 2122103 1221230 has eigenvalues cth = {10.4,0, -0.2, -0.6, -2.2, -3.4, -4}, which were calculated numerically. Exact eigenvalues could be obtained using Cardano's formula. One can easily verify that vector wh = [1/2, -1/2, 1/2, -1/2, 1/2, 0, 0]T solves the equation HwH = e. Since wHe 1/2, by Theorem 1.1 the graph H is an EDM-graph. 2 G. Jaklic and J. Modic: On minimal forbidden subgraphs for the class of EDM-graphs 163 5 6 20 5 Figure 9: A subdivision of the graph g520). References [1] R. Balaji and R. B. Bapat, Block distance matrices, Electron. J. Linear Algebra 16 (2007), 435-443. [2] J. Dattorro, Convex Optimization and Euclidean Distance Geometry, Meboo, 2008. [3] G. H. Golub and C.F. van Loan, Matrix computations, Johns Hopkins Studies in the Mathematical Sciences, third ed., Johns Hopkins University Press, 1996. [4] J. C. Gower, Euclidean distance geometry, Math. Sci. 7 (1982), 1-14. [5] T. L. Hayden, R. Reams and J. Wells, Methods for constructing distance matrices and the inverse eigenvalue problem, Linear Algebra Appl. 295 (1999), 97-112. [6] G. Jaklic, J. Modic, On properties of cell matrices, Appl. Math. Comput. 216 (2010), 20162023. [7] G. Jaklic, J. Modic, A note on "Methods for constructing distance matrices and the inverse eigenvalue problem", Linear Algebra Appl. 437 (2012), 2781-2792. [8] G. Jaklic and J. Modic, Inverse eigenvalue problem for Euclidean distance matrices of size 3, Bull. Aust. Math. Soc. 87 (2013), 82-93. [9] G. Jaklic and J. Modic, On Euclidean distance matrices of graphs, Electron. J. Linear Algebra 26 (2013), 574-589. [10] G. Jaklic, J. Modic, Euclidean graph distance matrices of generalizations of the star graph, Appl. Math. Comput. 230 (2014), 650-663. [11] G. Jaklic, J. Modic, Cartesian products of EDM-graphs, submitted. [12] B. D. McKay, Practical Graph Isomorphism, Congr. Numer. 30 (1981), 45-87. [13] I. J. Schoenberg, Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), 522-536. [14] G. Young, A. Householder, Discussion of a set of points in terms of their mutual distances, Psychometrika 3 (1938), 19-22.