A simple graph \(G\) with \(p\) vertices is said to be vertex-Euclidean if there exists a bijection \(f: V(G) \rightarrow \{1, 2, \ldots, p\}\) such that \(f(v_1) + f(v_2) > f(v_3)\) for each \(C_3\)-subgraph with vertex set \(\{v_1, v_2, v_3\}\), where \(f(v_1) < f(v_2) < f(v_3)\). More generally, the vertex-Euclidean deficiency of a graph \(G\) is the smallest integer \(k\) such that \(G \cup N_k\) is vertex-Euclidean. To illustrate the idea behind this new graph labeling problem, we study the vertex-Euclidean deficiency of two new families of graphs called the complete fan graphs and the complete wheel graphs. We also explore some related problems, and pose several research topics for further study.
On a triangle, the sum of the lengths of any two sides is greater than the length of the third side. This motivates us to call a simple graph \(G\) with \(q\) edges edge-Euclidean if it admits a bijective edge labeling \(f:E(G)\rightarrow\{1,2,\ldots,q\}\) such that on any \(C_3\)-subgraph with edges \(e_1\), \(e_2\) and \(e_3\), where \(f(e_1)<f(e_2)<f(e_3)\), we have \(f(e_1)+f(e_2)>f(e_3)\). As a result, the edge labels of any triangle satisfy the triangle inequality. The edge labeling \(f\) is called an edge-Euclidean labeling of the graph \(G\). For example, the graph displayed below on the left is not edge-Euclidean, but the graph on the right is.
Let \(L_k\) denote the null graph with \(k\) isolated vertices, each of them is incident to a loop. If a graph \(G\) is not edge-Euclidean, its edge-Euclidean deficiency or discrepancy, denoted \(\mu_e(G)\), is the smallest integer \(k\) so that \(G\cup L_k\) is edge-Euclidean. Hence, a simple graph \(G\) is edge-Euclidean if and only if \(\mu_e(G)=0\). The graph below on the left is not edge-Euclidean, its edge-Euclidean deficiency is 1, as indicated on the right below.
We have just started to study this new labeling problem, and discover many interesting properties that will appear in a series of forthcoming papers.
Note that we can define \(\mu_e(G)\) as the smallest integer \(k\) such that \(G\) admits a bijection edge labeling \(f:E(G)\rightarrow \{k+1,k+2,\ldots,k+q\}\) such that on any \(C_3\)-subgraph with edges \(e_1\), \(e_2\) and \(e_3\), where \(f(e_1)<f(e_2)<f(e_3)\), we have \(f(e_1)+f(e_2)>f(e_3)\). Since all the results we have derived thus far are based on the original definition, we will stay with it for consistency.
Meanwhile, we also begin to study of the vertex analog of this problem.
Definition 1. A simple graph \(G\) with \(p\) vertices is said to be vertex-Euclidean if there exists a bijection \(f:V(G) \rightarrow \{1,2,\ldots,p\}\) such that, on any \(C_3\)-subgraph on the vertices \(v_1, v_2, v_3\), where \(f(v_1) < f(v_2) < f(v_3)\), we have \[f(v_1) + f(v_2) > f(v_3).\] In other words, the vertex labels on any \(C_3\)-subgraph satisfy the triangle inequality.
It is obvious that \(C_3\) itself is not vertex-Euclidean, because when its three vertices are labeled with 1, 2, and 3, we find \(1+2 \not> 3\). Any \(C_3\)-free graph is, by default, vertex-Euclidean. However, a graph that contains a \(C_3\)-subgraph may still be vertex-Euclidean. Here is an example:
In general, if a graph contains a \(C_3\)-subgraph, the label 1 cannot be used on any one of its three vertices. The reason is: if the three vertices of the \(C_3\)-subgraph are labeled 1, \(x\), and \(y\), where \(1<x<y\), then \(x+1\leq y\). Thus, \(1+x \not> y\).
A graph is said to be triangulated if every vertex lies on a \(C_3\)-subgraph. It follows that a triangulated graph cannot be vertex-Euclidean.
Definition 2. The vertex-Euclidean deficiency or discrepancy of a graph \(G\) is the smallest integer \(k\) such that \(G \cup N_k\) (where \(N_k\) denotes the null graph on \(k\) vertices) is vertex-Euclidean, and we write \(\mu_v(G)=k\).
For example, a graph \(G\) is vertex-Euclidean if and only if \(\mu_v(G)=0\). It is easy to see that \(\mu_v(C_3)=1\).
We also find \(\mu_v(K_4)=2\). The reason is: if \(\mu_v(K_4)=1\), then the four vertices of \(K_4\) will be labeled 2, 3, 4, and 5. Since \(2+3\not>5\), this labeling is not vertex-Euclidean. Thus, the smallest label on \(K_4\) is 3. This shows that \(\mu_v(K_4) \geq 2\).
It is easy to find a vertex-Euclidean labeling with two isolated vertices.
This observation can be generalized.
Theorem 1. For any integer \(n\geq3\), we have \(\mu_v(K_n) = n-2\).
Proof. Let \(x\) be the smallest label on the vertices of \(K_n\). Then the next smallest label is \(x+1\), and the largest label is \(x+n-1\). On the \(C_3\)-subgraph on these three vertices, we find \[x + (x+1) > x+n-1 .\] Therefore, \(x>n-2\), which implies that we need \(k=n-2\) isolated vertices for \(K_n\cup N_k\) to be vertex-Euclidean. ◻
Corollary 1. If \(G\) is connected, with \(p\) vertices, then \(\mu_v(G) \leq p-2\).
Proof. It is clear that if \(H\) is a subgraph of \(G\) with the same number of vertices, then \(\mu_v(H)\leq\mu_v(G)\). Since \(G\) is a subgraph of \(K_p\), the result follows immediately. ◻
In this exposition, we study the vertex-Euclidean deficiency of two new families of graphs defined below. They illustrate why the problem is not as simple or direct as it may appear to be. We also introduce some related problems for further study.
The join of two graphs \(G_1\) and \(G_2\) (see, for example, [1]) is constructed from \(G_1\) and \(G_2\) by joining each vertex of \(G_1\) to each vertex in \(G_2\). It is also called the Zykov sum of \(G_1\) and \(G_2\) [2], and is denoted \(G_1+G_2\). For example, the complete bipartite graph \(K_{m,n}\) is the join \(N_m+N_n\). The join \(P_n+N_1\) is called a fan graph. It is formed by connecting an isolated vertex to every vertex on the path \(P_n\). Below are the graphs \(F_n\cup N_1\) for \(n=2,3,4,5,6\):
It appears that \(\mu_v(F_n)=1\) for all integers \(n\geq2\). Since each fan graph is triangulated, \(\mu_v(F_n)\geq1\). To show that \(F_n\cup N_1\) is vertex-Euclidean, we first label the isolated vertex \(w_1\) with 1. Next, label the left-most \(C_3\)-subgraph with 2, 3, and 4, such that the edge it shares with the next \(C_3\)-subgraph is labeled 3 and 4. Label the remaining vertices with 5, 6, … . The result is a vertex-Euclidean labeling. Thus, \(\mu_v(F_n)=1\).
A fan graph can be viewed as an array of \(K_3\)s, aligned in a way that neighboring \(K_3\)s share a common edge. Inspired by this observation, we extend the idea to an array of complete graphs \(K_m\)s. Again, we demand that neighboring copies of \(K_m\)s should share a common edge, similar to the neighboring \(K_3\)s in a fan graph. This produces the complete fan graph \(K_m F_n\). Hence, the complete fan graph \(K_m F_n\) is essentially an array of \(n-1\) copies of the complete graphs \(K_m\). A precise definition is given below.
Definition 3. For \(m\geq3\) and \(n\geq2\), define the complete fan graph \(K_m F_n\) as follows.
Let \(V(K_m F_n) = \{c\} \cup \{v_1,v_2,\ldots,v_n\} \cup \{v_{i,1},v_{i,2},\ldots,v_{i,m-3} \mid 1\leq i\leq n-1\}\).
The edge set \(E(K_m F_n)\) consists of the edges that form a complete graph \(K_m\) on the vertex set \(\{c,v_i,v_{i+1},v_{i,1}, \ldots,v_{i,m-3}\}\) for \(1\leq i\leq n-1\).
Notice that
the vertex set \(\{c,v_1,v_2,\ldots,v_n\}\) induces the fan graph \(F_n\), \(K_m F_n = F_n\) when \(m=3\);
\(K_m F_n = K_m\) when \(n=2\); and
any adjacent complete graphs \(K_m\) share a common edge of the form \(c v_i\), where \(2\leq i\leq n-1\).
Below are the graphs \(K_4 F_n\cup N_2\) for \(n=2,3,4,5,6\):
In each case, we find \(\mu_v(K_4 F_n) = 2\).
In general, since \(K_4 F_n\) contains at least one copy of \(K_4\), we know that \(\mu_v(K_4 F_n) \geq \mu_v(K_4) = 2\). To show that \(K_4 F_n \cup N_2\) is vertex-Euclidean, we first label the two isolated vertices \(w_1\) and \(w_2\) with the integers 1 and 2. Next, label the left-most copy of \(K_4\) with the integers 3, 4, 5, and 6, so that \(c\) is labeled 6, and the highest labels 5 and 6 occupy the edge between the first two \(K_4\)s. Next, label the remaining vertices of the second \(K_4\) with 7 and 8, such that the highest label 8 is adjacent to \(c\). This ensures that the edge between the second and third copies of \(K_4\) is incident to \(c\) and the highest label that has been used thus far. Repeat this until all vertices have been labeled. The result is a vertex-Euclidean labeling of \(K_4 F_n \cup N_2\). This proves that \(\mu_v(K_4 F_n) = 2\).
Below are the graphs \(K_5 F_n\cup N_3\) for \(n=2,3,4,5\):
The algorithm described above shows that \(\mu_v(K_m F_n) = m-2\) for all integers \(m\geq3\) and \(n\geq2\).
The wheel graph \(W_n\) is formed by connecting an isolated vertex to every vertex of the cycle \(C_n\). In other words, \(W_n =C_n + N_1\). This is similar to the fan graph except that the two \(C_3\) on the far left and far right wrap around to form a wheel. The result is a circular array of \(n\) copies of \(C_3\)s so that adjacent copies share a common edge. Here are \(W_3\), \(W_4\), and \(W_5\):
We can form the complete wheel graph \(K_m W_n\), similar to the construction of \(K_m F_n\). For \(K_m W_n\) to be well-defined, we need \(m,n\geq3\). Naturally, \(K_m W_n = W_n\) when \(m=3\). The complete wheel graphs \(K_4 W_n\), where \(m=4,5\) and \(n=3,4,5\), are displayed below.
Unlike the complete fan graphs, the complete graphs \(K_m\)s wrap around to produce a wheel-like structure. This could produce \(\mu_v(K_m W_n) > m-2\).
Even the vertex-Euclidean deficiency of the wheel graph does not appear to be obvious:
The complete wheel graphs are more complicated:
One more example:
The exact value of \(\mu_v(K_m W_n)\) remains unknown. We invite the readers to determine its value.
We now turn our attention to other related problems. We introduce the notation \(\\mbox{vEuclid}(k)\) for the set of all connected graphs \(G\) with \(\mu_v(G)=k\). We say a graph \(G\) is critically vertex-Euclidean if \(\mu_v(G)=k\), and \(\mu_v(G-v)=k\) for any vertex \(v\) in \(G\), and use the notation \(\mbox{vCritEuclid}(k)\), or simply \(\\mbox{vEuclid}^*(k)\) to indicate the set of all critically vertex-Euclidean graphs with \(\mu_v(G)=k\). Obviously, if \(G\in\mbox{vEuclid}(0)\), then we also have \(G\in\\mbox{vEuclid}^*(0)\). It is not obvious that \(\\mbox{vEuclid}^*(k)\neq\emptyset\) if \(k\neq0\). Examples can be drawn from the composition (also called dictionary or lexicographic product) of two graphs.
Given two graphs \(G_1=(V_1,E_1)\) and \(G_2=(V_2,E_2)\), the composition \(G_1[G_2]\) is the graph with \(V_1\times V_2\) as its vertex set, and the vertices \((u_1,v_1)\) and \((u_2,v_2)\) are adjacent if
\(u_1 u_2 \in E(G_1)\), or
\(u_1=u_2\), and \(v_1 v_2 \in E(G_2)\).
See, for example, [1]. The composition \(C_4[P_2]\) is given below.
One can show that \(\mu_v(C_3[N_3])=5\):
Due to symmetry, it suffices to study \(C_3[N_3]-v\) for any vertex \(v\):
Since \(\mu_v(C_3[N_3]-v)=5\), we deduce that \(C_3[N_3]\in\\mbox{vEuclid}^*(5)\).
Many graphs are not critically vertex-Euclidean. These graphs have the property that the removal of a single vertex would change their vertex-Euclidean deficiency. The deficiency of \(G-v\) may depend on the choice of \(v\). Let \(S\) be a set of integers. We use the notation \(\\mbox{vEuclid}^*(k\downarrow S)\) for the set of all connected graphs \(G\) with \(\mu_v(G)=k\), and \(S\) is the minimal set that contains all possible values of \(\mu_v(G-v)\) taken over the vertices \(v\) in \(G\). For example, we find \(K_3 F_3 \in \\mbox{vEuclid}^*(1\downarrow\{1,0\})\):
Here, we use an asterisk to indicated the removed vertex. We also have \(K_3 F_4 \in \\mbox{vEuclid}^*(1\downarrow\{1,0\})\):
We find \(K_4 F_3, K_4 F_4 \in \\mbox{vEuclid}^*(2\downarrow\{1\})\):
We also find \(K_5 F_3, K_5 F_5 \in \\mbox{vEuclid}^*(3\downarrow\{2\})\):
and \(K_6 F_4 \in \\mbox{vEuclid}^*(4\downarrow\{3\})\):
Conjecture 1. \[K_m F_n \in \left\{\begin{array}{ll} \\mbox{vEuclid}^*(1\downarrow\{1,0\}) & \mbox{if } n=3, \\ \\mbox{vEuclid}^*(n-2\downarrow\{n-3\}) & \mbox{if } n\geq4. \end{array}\right.\]
The behavior of the complete wheel graphs \(K_m W_n\) is more complex. We find \(K_3 W_3 \in \\mbox{vEuclid}^*(1)\):
However, we have \(K_3 W_4 \in \\mbox{vEuclid}^*(2\downarrow\{1,0\})\):
We also find \(K_3 W_5 \in \\mbox{vEuclid}^*(2\downarrow\{1,0\})\):
However, we have \(K_3 W_6 \in \\mbox{vEuclid}^*(3\downarrow\{2,0\})\):
We also find \(K_3 W_7 \in \\mbox{vEuclid}^*(3\downarrow\{2,0\})\):
However, we have \(K_3 W_8 \in \\mbox{vEuclid}^*(4\downarrow\{3,0\})\):
Unexpectedly, we find \(K_3 W_9 \in \\mbox{vEuclid}^*(5\downarrow\{4,0\})\):
The behavior becomes more complex when \(m=4\). We have found that \(\mu_v(K_4 W_3) = 2\):
We find \(K_4 W_3 \in \\mbox{vEuclid}^*(2\downarrow\{2,1\})\):
We know that \(\mu_v(K_4 W_4)=2\):
But we have \(K_4 W_4 \in \\mbox{vEuclid}^*(2\downarrow\{3,2,1\})\):
What if \(m=5\)? We know that \(\mu_v(K_5 W_4) = 4\). We find \(K_5 W_4 \in \\mbox{vEuclid}^*(4\downarrow\{3,2\})\):
Let us consider yet another example. We know that \(\mu_v(K_6 W_5) = 4\). There are three possible choices for the removed vertex. They are listed in Figure 1. We determine that \(K_6 W_5 \in \\mbox{vEuclid}^*(4\downarrow\{4,3\})\).
The case of \(K_m W_n\) appears to be rather complex. We invite the readers the study these problems.
There are many problems that we can study.
Determine the vertex-Euclidean deficiency of other families of graphs.
The construction of other vertex-Euclidean and non-vertex-Euclidean graphs.
For any integer \(n\), we know that \(\mu_v(K_{n+2})=n\). What is the maximum number of edges that we can remove from \(K_{n+2}\) without altering the vertex-Euclidean deficiency?
We can study other extremal problems similar the one we just mentioned. For example, what is the maximum number of edges on a connected graph \(G\) with \(p\) vertices so that \(\mu_v(G) < p-2\)?
Study the analogous problems for \(\mu_e(G)\).
We are indebted to the anonymous referee, whose comments and suggestions provide valuable insights that lead to the improvement of the manuscript.
The authors declare no conflict of interest.