The dimension of a graph

The dimension of a graph L. Boza 1 Dep. Matem´atica Aplicada I Universidad de Sevilla Sevilla, Spain M.P. Revuelta 2 Dep. Matem´atica Aplicada I Universidad de Sevilla Sevilla, Spain Abstract For each graph Gthe dimension of Gis defined as the smallest dimension in the Euclidean Space where there is an embedding in which all the edges of Gare segments of a straight line of length one. The exact value is calculated for some important families of graphs and this value is compared with other invariants. An infinite quantity of forbidden graphs for dimension 2 is also shown. Keywords: Dimension, graphs, complete graphs, multipartite graphs, invariants. 1 Introduction Let Gbe a graph. The dimension of graph G, denoted by dim(G), is defined as the smallest natural number n∈Nsuch that Ghas an embedding in Rn 1 Email: [email protected] 2 Email: [email protected] where all the edges of Gare segments of a straight line of length one. In this work the exact values of the dimension of graph Gare calculated for some important families of graphs: the complete graphs, the bipartite complete and the tripartite complete graphs. This value is also compared with other invariants: the chromatic number and the genus of a graph. In addition, bounds of the dimension are given by planar and outerplanar graphs. It is easy to check that the graphs with dimension of maximum n, with n> 1, can neither be characterized by minors nor even by forbidden topological minors. The following question arises: Can the graphs with dimension of maximum nbe characterized by a finite quantity of forbidden subgraphs? A negative answer is obtained by showing an infinite family of forbidden graphs for dimension 2. 2 Dimension of some families of graphs In this section the exact values of the dimension of graph Gare calculated for some important families of graphs. 2.1 Dimension of the complete graphs In the following result the dimension of a complete graph is obtained. Theorem 2.1 dim(Kn)=n−1 Proof. The following npoints are considered in the Euclidean Space Rn−1,y0= (0,0,0, ..., 0),...,y k=(z1,z 2, ..., zk−1,(k+1)zk,0, ..., 0), where k=1,2, ..., n− 1 and zk=1 √2k(k+1). One can easily check that these npoints in Rn−1are at distance one. Therefore dim(Kn)≤n−1. We can prove, by induction in n, that the embedding of these points is unique up to movements. Given npoints in Rn−1, let us take the first n−1 points. They are contained in a lineal variety of dimension n−2. By a movement, this variety can be taken to the hyperplane Xn−1= 0. As this variety is isomorphic to Rn−2, by hypothesis of induction it can be supposed that these first n−1 points are y0,...,y n−2, by adding the value 0 as the (n−1)-th coordinate. It is not difficult to show, by induction in the component, that the two unique points of Rn−1that are at distance one from the n−1 previous points are yn−1=(z1,...,z n−1,nz n−1) and (z1,...,z n−1,−nzn−1). By making a symmetry with respect to the hyperplane Xn−1=0,then−2 previous vertices become invariant, while the two last points transform into each other. As a consequence of the uniqueness of the embedding and since the points y0,...,y n−1are not contained in a lineal variety of dimension n−2, dim(Kn)>n−2 and therefore the result is obtained. 2 The following consequences are deduced from the previous result: Corollary 2.2 The embedding of Knin Rn−1is unique up to movements. Corollary 2.3 Given nvertices in Rnsuch that the distance between any pair of vertices is equal to 1, there are only two vertices whose distance is 1 from all the vertices. Corollary 2.4 Let xbe an edge of Kn,dim(Kn−x)=n−2. Furthermore, the following result is also obtained: Corollary 2.5 dim(P7+K2)=4. Proof. Let us suppose the opposite case where the graph P7+K2has an embedding in R3. This graph has 9 vertices and the edge u1u2,vivi+1, with i=1,...,6, and uivj, with i=1,2 and j=1,...,7. The vertices u1,u2,v1and v2induce K4. It can be supposed that their coordinates are (0,0,0), (1,0,0), (1 2,√3 2,0) and (1 2,√3 6,√6 3). From Corollary 2.3, given 3 points which form an equilateral triangle of unitary sides, only two points exist that are at distance 1 from all the points in R3. Hence, it can be deduced that given the points u1,u2and vi, with i<1, two points will exist at distance 1 from all of the points. These are vi−1 and vi+1. The coordinates of the vertices vi, with i=3,...,7, are respectively, (1 2,−7√3 18 ,2√6 9), (1 2,−23√3 54 ,−5√6 27 ), (1 2,17√3 162 ,−28√6 81 ), (1 2,241√3 486 ,−11√6 243 ) and (1 2,−329√3 1458 ,230√6 729 ). In this case, segments v1v2and v6v7intersect at (1 2,23√3 66 ,5√6 33 ), therefore a contradiction is obtained. An embedding of P7+K2in R4, can be given by assigning the coordinates (1 2,2433√3 658 ,0,√36894 329 )tov7and by conserving the coordinates of the other vertices. 2.2 Dimension of the multipartite complete graphs Let us now enunciate the result that indicates the dimension of the bipartite complete graphs: Theorem 2.6 (i) dim(Km,n)=4,con3≤m≤n. (ii) dim(K2,n)=3,conn≥3. (iii) dim(K1,n)=2,sin≥2. (iv) dim(K1,1)=1. Items ii,iii and iv are straightforward. Item iwill be proved in the next section. The following result calculates the dimension of the tripartite complete graphs: Theorem 2.7 (i) dim(Km,n,p)=6,con3≤m≤n≤p. (ii) dim(Km,n,p)=5,conm≤2y3≤n≤p. (iii) dim(Km,2,p)=4,conm≤2yp≥3. (iv) dim(Km,2,2)=3,conm≤2. (v) dim(K1,1,p)=3,conp≥3. (vi) dim(K1,1,p)=2,conp≤2. 3 Relationship between the dimension and other invariants In this section we study if a graph has a given invariant then the dimension of a graph is bounded or if a graph has a given dimension then the invariant of a graph is bounded. First, we relate the dimension of a graph with the chromatic number of a graph: Lemma 3.1 dim(G)≤2χ(G). Corollary 3.2 If there exists a coloring of the vertices of Gwith χ(G)colors so that there exist kcolors that have been assigned to a maximum of 2 vertices, then dim(G)≤2χ(G)−k. Corollary 3.3 dim(Kp1,...,pk,pk+1,...,pk+h)≤k+2h, when p1≤... ≤pk<3≤ pk+1 ≤...≤pk+h. As was seen in Theorems 2.6 and 2.7, in some cases the inequality is strict and in other cases it is an equality. From this result we can approach the proof of item iof Theorem 2.6. Proof. By Corollary 3.3 dim(Km,n)≤4 is obtained. On the other hand, it is clear that dim(Km,n)≥dim(K3,3), therefore it is enough to prove that dim(K3,3)≥4. Let us suppose the opposite. An embedding of K3,3in R3exists with all the edges of length 1. Three disjoint vertices are considered taken two by two, and the three spheres whose radii are equal to 1, centered in these vertices. Two of these spheres intersect, a maximum of a circle and this circle intersects with the other sphere at a maximum of two points. However, an adjacent vertex with the centers of the 3 spheres has to be in their intersection, therefore there would be a maximum of two of these vertices and a contradiction would be obtained. Hence the result holds. By Four Colors’s Theorem (see [1]), we know that if a graph is plane then its chromatic number is at most 4, therefore the following result is obtained: Corollary 3.4 If Gis a plane graph then dim(G)≤8. One open problem is to calculate the maximum value that the dimension of a plane graph can have. By Corollary 2.5 and 3.4, we know that this number ranges from 4 to 8. As the chromatic number of the outerplanar graphs is at most 3, the dimension of the outerplanar graphs is at most 6. However this result can be improved in the following way: Theorem 3.5 If Gis an outerplanar graph, then dim(G)≤3. Proof. Let us suppose that the result is not true and that Gis the smallest outerplanar graph with dim(G)>3. Ghas a vertex vof degree 2. Let G be a graph which is obtained when the vertex vof Gis removed and the edge between uand wis added(uand ware the neighbors of v). Gis an outerplanar graph and it has a vertex less than G, hence dim(G)≤3. An embedding of Gin R3is considered with all the unitary edges and such that uand ware at distance 1. Since there are infinite points in R3which are at distance 1 from uand w, vertex vcan be placed at one of them, where the edges uv and wv don’t intersect with the rest of the graph. Therefore we would have an embedding of Gin R3with all the unitary edges which is a contradiction. This result cannot be improved, since it is easy to check that dim(K1+ P6)=3. Let us relate the dimension of a graph with the genus of a graph (remember that the genus of a graph is the smallest genus on the compact surfaces where the graph admits an embedding). The following result is required: Proposition 3.6 (i) Let Gbe a graph, there exists a subdivision of G, denoted by S(G), such that dim(S(G)) = 3. (ii) Let Gbe a planar graph, there exists a subdivision of G, denoted by S(G), such that dim(S(G)) = 2. Proof. It is clear that any finite graph can be represented in R3so that their edges are segments of a straight line. In addition, the complete graph whose cardinal is the continuous 2ℵ0, can also be represented in this way (see [3]). On the other hand, all finite planar graphs can be represented in R2such that all the edges are segments of a straight line (see [4]). Let us distinguish three cases: Case 1: The lengths of the edges are natural numbers. In this case the edges are subdivided such that all edges have length 1. Case 2: The lengths of the edges are rational numbers. If the lengths of the edges are rational numbers then a homothecy of dilation factor the minimum common multiple of the denominators of rational numbers is considered and the previous case is applied. Case 3: The lengths of the edges are irrational numbers. If some of the lengths of the edges are irrational numbers, then an edge xwith irrational length lxand a rational number rsufficiently near to lx 2are taken, such that xcan be replaced by two new adjacent edges of length r. Therefore, these edges are sufficiently near to the edge xsuch that these edges don’t intersect with the rest of the edges of the graph. By repeating the process with all the edges of irrational length, a subdivision of the graph is obtained with all the edges of rational length and the previous case is applied. Considering an appropriate subdivision of any graph with genus n≥1, graphs with genus nand with dimension 3 can be found. However, there exists an upper bound of the dimension in function of the genus, as the following result shows: Proposition 3.7 dim(G)≤27+√1+48γ(G) 2. Proof. Ringel and Youngs in [2] proved that χ(G)≤7+√1+48γ(G) 2. By Lemma 3.1, the result is obtained. 4 Finite or infinite set of the forbidden graph of bounded dimension A forbidden graph in a partial order for a specific property, is a graph that doesn’t have the property, however any smaller graph, in this partial order, has this property. It is clear that the graph with the property ”to have a maximum dimension of 1” can be characterized by forbidden minors. The unique forbidden finite graphs are K1,3and K3. There is one forbidden numerable graph: •The graph composed of two connected components, each one of which is an infinite path and an infinite numerable quantity, ℵ0, of the disjoint edges. There are also two forbidden non numerable graphs: (i) The graph composed of ℵ1(the cardinal ℵ0), disjoint edges. (ii) The graph composed of 2ℵ0(the cardinal following the cardinal of the continuum) disjoint vertices (in the generalized continuum hypothesis this cardinal is ℵ2). However, even in the finite case, the graphs with the property ”to have a maximum dimension of 2” are not been able to characterize by forbidden minors, not even by topological forbidden minors. Logically, these graphs are been able to characterize by forbidden subgraphs. The question arises in a natural way: Is the forbidden subgraph set for the property ”to have a maximum dimension of 2” finite or not?. The answer is negative, as we can deduce from the following result: Theorem 4.1 The graphs in the Figure 1are forbidden graphs with the property ”to have a maximum dimension of 2” with n≥2.  JJJ J JJJ J JJJ J JJJ J ... ... JJJ J  ... tt tt tt tt tt tttt u1u2un−1un v0=w0vn=wn v1v2vn−1 vn−2 w1w2wn−1 wn−2 Fig. 1. Forbidden graphs with the property ”to have a maximum dimension of 2” Proof. Since K3has an unique embedding in R2up to movements, it is easy to see that, extending this embedding, the graph minus the edges wkwk+1, with k=0,...,n−1, has an unique embedding in R2. In this embedding the vertices v0and vnare at distance n−1, therefore extending this embedding to the graph, the edges wkwk+1 are overlapped on vkvk+1, hence the dimension of the graph has to be bigger than 2. On the other hand, it is not difficult to find an embedding in R2when an edge is eliminated. It is enough to consider four cases depending on the type of eliminated edge: ukuk+1,vkvk+1,wkwk+1 and ukvkor uk+1vk. As a consequence the following result is obtained: Corollary 4.2 The forbidden graph set with the property ”to have a maximum dimension of 2” is infinite. References [1] APPEL, K. y HAKEN, W. Every planar map is four colorable.. Illinois J. Math. 21, 429-567, 1977. [2] RINGEL, G. y YOUNGS W. T. Solution of the Heawood map-coloring problem. Proc. Nat. Acad. Sci. USA, 60, 438-445, 1968. [3] THOMASSEN, C. Infinite graphs. Further Selected Topics in Graph Theory. Academic Press, Londres, 129-160, 1983. [4] WAGNER, K. Bemerkungen zum Vierfarbenproblem. Jber. Deutsch. Math.- Verein, 26-32, 1936.