Dimensions of a Graph

Introduction

In the book we have read on page 93 Erdös’s Open Problem 13.12: ‘What is the smallest number of edges in a graph G, such that dimG = 4?’ [1].

That gives the cause to introduce some constants, which are all elements of the natural numbers N := {1, 2, 3,...}.

We assume that the reader is familiar with the concepts of graphs, edges, and vertices.

A display of an abstract graph G means an isomorphic graph H in Rm for any m such that the edges are line segments, and H has a finite number of intersection points.

Definitions

We repeat the definitions of four 'dimensions'.

Let G be a connected finite graph.

Definition 1. The dimension dim(G) is the minimum natural number k such that there is a display of an isomorphic graph H in Rk, and all pairs of adjacent vertices in H have the same distance. Please see [1,2].

The symbol Edim(G) means the same, except that all pairs of vertices of G which are adjacent have the same distance, while pairs that are not adjacent have other distances. See [1].

The edge distance of two vertices ^→a and ^→b in a graph G is defined as the minimum number of edges in a way from ^→a to ^→b.

The dimension mdim(G) is defined as the smallest cardinality of a resolving set R, where a resolving set is a subset of the vertices of G. It has the property that for each pair (^→a, ^→b) of vertices of G where ^→a ≠ ^→b, there is ^→r ∈ R such that the edge distance between ^→a and^→r differs from the edge distance between ^→b and^→r . In the case that there is no resolving set we write mdim(G) = ∞. See the papers [3,4].

The distance from a vertex ^→v to an edge e with endpoints ^→a and ^→b is the minimum of the edge distances between ^→a and ^→v and ^→b and ^→v, respectively. We call this number d(^→v,e).

The number edim(G) is defined as the smallest cardinality of an edge resolving set E, where an edge resolving set is a subset of the vertices of G. It has the property that for each pair (f,g) of edges of G where f ≠ g, there is^→r ∈ E such that d(^→r, f ) |¸=d(^→r, g). In the case that there is no edge resolving set we write edim(G) = ∞. See [5,6].

We define eight sequences of natural numbers. The number n is an element of N.

Definition 2.

vertex dim(n) := The smallest natural number of the cardinality of the set of vertices of a graph G such that dim(G) = n.

vertex Edim(n) := The smallest natural number of the cardinality of the set of vertices of a graph G such that Edim(G) = n.

vertex mdim(n) := The smallest natural number of the cardinality of the set of vertices of a graph G such that mdim (G) = n.

vertex edim(n) := The smallest natural number of the cardinality of the set of vertices of a graph G such that edim(G) = n.

edge dim(n) := The smallest natural number of the cardinality of the set of edges of a graph G such that dim(G) = n.

edge Edim(n) := The smallest natural number of the cardinality of the set of edges of a graph G such that Edim(G) = n.

edge mdim(n) := The smallest natural number of the cardinality of the set of edges of a graph G such that mdim(G) = n.

edge edim(n) := The smallest natural number of the cardinality of the set of edges of a graph G such that edim(G) = n.

Let S be a graph that has no edges.

We define dim(S) := E

dim(S) := edim(S) := 1

Some Propositions

Proposition 1: It holds vertex dim(1) = vertex Edim(1) = 2 and vertex dim(2) = vertex Edim(2) = 3 and vertex dim(3) = vertex Edim(3) = 4                                                                                                                                                                                                                 

Proof. The complete graphs K2, K3, and K4 establish the proposition.

Proposition 2: It holds edge dim(1) = edge Edim(1) = 1, edge dim (2) = edge Edim(2) = 3, and edge dim(3) = edge Edim(3) = 6

Proof. The first two claims are trivial.

Graph K4 has a dimension of 3, see [1], p. 88, while graphs with fewer edges and four vertices have a smaller dimension since we can embed them in R2. This shows edge dim (3) = edge Edim(3) = 6, the number of edges of K4.                                                               

We can calculate vertex dim(n).

Proposition 3: It holds vertex dim(n) = n + 1 for all natural numbers n.

Proof. From [1], p. 88, we get dim (Kn+1) = n. The graph K_n+1 has n+1 vertices. Every graph with fewer vertices is isomorphic to a

subgraph of K_n.                                                                                                                                                                                          

Conjecture. For all n ∈ N it holds vertex Edim(n) = n+1 and edge dim(n) = edge Edim(n) = 1/2 . n . (n + 1). We believe that we need K_n+1.

Points

There is a well-known riddle ‘Place 9 points in the plane, such that 8 of them form a square, and the 9. point is the center, such that there are 8 sets of 3 collinear points. Now draw 4 line segments through all points. The line segments are connected.’ We generalize the riddle to an infinite set of questions.

Let n be a natural number. We place n points anywhere in the plane on fixed positions. We call this P(n). Note that for each n, P(n) describes infinite many placements.

We define that a polygon line consists of a finite number of line segments and it is homeomorphic to a line segment.

We define that a zig-zag line consists of a finite number of line segments. Every line segment is connected at both ends with another line segment (with the exception of the first and the last one). It may self-intersect.

We define a right-angle line as a polygon line and each piece either is horizontal or vertical.

We define a rectangle line as a zig-zag line such that each piece either is horizontal or vertical. It may self-intersect.

We define for each placement P(n) of n points eight constants.

• Let denote C(P(n)) be the least natural number k such that all points of P(n) are a subset of a polygon line, which consists of k line segments.

• Let denote D(P(n)) be the least natural number k such that all points of P(n) are a subset of a zig-zag line, which consists of k line segments.

• Let denote E(P(n)) be the least natural number k such that all points of P(n) are a subset of a right-angle line, which consists of k line segments.

• Let denote F(P(n)) be the least natural number k such that all points of P(n) are a subset of a rectangle line, which consists of k line segments.

• Let denote G(P(n)) be the least natural number k such that all points of P(n) are a subset of a polygon line, which consists of k line segments, and each point is a subset of a single line segment from the polygon line.

• Let denote H(P(n)) be the least natural number k such that all points of P(n) are a subset of a zig-zag line, which consists of k line segments, and each point is a subset of a single line segment.

• Let denote I(P(n)) be the least natural number k such that all points of P(n) are a subset of a right-angle line, which consists of k line segments, and each point is a subset of a single line segment.

• Let denote J(P(n)) be the least natural number k such that all points of P(n) are a subset of a rectangle line, which consists of k line segments, and each point is a subset of a single line segment.

Proposition 4: For a natural number n all just defined eight constants are less or equal 2·n.

Proof. We will construct a right-angle line that consists at most of 2·n line segments, where the points are a subset of the line, and every point is a subset of a single line segment. This example fulfills the conditions for the situations to estimate all constants which we just have defined above.

We assume n points, which are placed anywhere on the plane. Every point is defined by two coordinates x and y. We assume that the points are ordered by their x coordinate. At first we assume that all x coordinates are different. We start with the first point. We go vertically and then horizontally to the second point. In this way, we connect all points. We use only horizontal and vertical line segments. In the case that some points have equal x coordinates, we draw one vertical line segment to connect them.

This means that we draw at most 2·n line segments, which do not intersect. We have drawn a right-angle line. The proof is finished.   

Figure 1: On the right-hand side is on the left a zig-zag line and on the right a polygon line

Figure 2: On the right-hand side on the left, we see a rectangle line and on the right, a right- angle line

The Thuerey Numbers

For all p € N we denote Kp as the complete graph with precisely p vertices.

Let G C R^k for any k be a graph. We define T(G)_n for all natural numbers n as the minimum number of colors to color G such that there is no monochromatic subgraph K_n. If this is not possible, we write T(G)n = 0 for this n.

Hence, we have defined a sequence T(X)_q(q € N) for all graphs

Figure 3: The riddle: Show D (P (9)) = 4

X. We call 'T(X)q(q € N)' the 'Thuerey Numbers'.

We summarize the open problems.

Open Problems

We ask for the sequences of Definition 2. We ask for the constants _xxx(P(n)) for any placement P(n), where _xxx is from {C, D, E, F, G, H, I, J}. Further, for a graph X we ask for the sequence T(X)_q(q ∈ N).

Acknowledgement

We thank Bouchra Ben Zahir for some calculations and Arne Thürey for support

References

[1]. Soifer, A. (2009). The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of its Creators, New York Springer, ISBN 978-0-387-74640-1.

[2]. Erdös, P., Harary, F., Tutte, W. T. (1965). ON THE DIMENSION OF A GRAPH, Mathematika, Vol. 12, Iss. 2, London.

[3]. Slater, P. J. (1975). Leaves of Trees, Congressus Numerantium. Harary, F., Melter, R. A. (1976). On the metric dimension of a graph, Ars Combin, 2 (191-195).

[4]. Kelenc, A., Tratnik, N., & Yero, I. G. (2018). Uniquely identifying the edges of a graph: The edge metric dimension,Discrete Applied Mathematics, 251, 204-220.

[5]. https://arxiv.org/pdf/1602.00291.pdf.

[6]. Soifer, A. (2024). The New Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of its Creators, New York Springer.