A \((p, g)\)-graph \(G\) is Euclidean if there exists a bijection \(f: V \to \{1, 2, \ldots, p\}\) such that for any induced \(C_3\)-subgraph \(\{v_1, v_2, v_3\}\) in \(G\) with \(f(v_1) < f(v_2) < f(v_3)\), we have that \(f(v_1) + f(v_2) > f(v_3)\). The Euclidean Deficiency of a graph \(G\) is the smallest integer \(k\) such that \(G \cup N_k\) is Euclidean. We study the Euclidean Deficiency of one-point union and one-edge union of complete graphs.
Definition 1. A \((p,g)\)-graph \(G\) is Euclidean if there exists a bijection \(f: V \to \{1,2,\ldots,p\}\) such that for any induced \(C_3\)-subgraph \(\{v_1,v_2,v_3\}\) in \(G\) with \(f(v_1) < f(v_2) < f(v_3)\), we have that \[f(v_1) + f(v_2) > f(v_3).\] Let \(\text{Euclid}(0)\) be the set of all Euclidean graphs.
Example 1. An Euclidean graph with 5 vertices:
Example 2. All triangle free graphs are Euclidean.
Example 3. Euclidean \((p,g)\)-graphs with \(p=1,2,\ldots,6\)
An immediate observation is that \(C_3\) is not Euclidean, for the vertices will be labeled with \(1,2,3\), but \(1+2\not>3\). This observation can also be extended: the label \(1\) cannot be used on any vertices contained in some \(C_3\) subgraph. For the sake of contradiction, assume this \(C_3\) subgraph is labeled \(1,x,y\) where \(1<x<y\), then \(1+x\leq y\) and hence \(1+x\not>y\) for any integer \(y>x\). It follows
That if all vertices are part of some \(C_3\) subgraph then, the graph must necessarily not be Euclidean.
Definition 2. The Euclidean deficiency of a \((p,g)\)-graph \(G\) is \(\min\{k: G \cup N_k \in \text{Euclid}(0)\}\), where \(N_k\) is the null graph with \(k\) vertices, and we’ll denote this number by \(\mu(G)\). For a given \(k > 0\), let \(\text{Euclid}(k)\) be the set of all graphs with Euclidean deficiency \(k\).
Example 4. Graphs with Euclidean deficiency 1:
Theorem 1. Let \(n \geq 3\) and \(K_n\) be the complete graph of order \(n\), then \(\mu(K_n) = n – 2\).
Proof. Observe letting the vertices having labels \(n – 1, n, \ldots, 2n – 1\) works, since \(n – 1, n\) are the smallest labels, it follows that, for label of any two vertices \(v_1, v_2\), \[f(v_1) + f(v_2) \geq n – 1 + n = 2n – 1,\] greater than all other labels. This establishes that \(\mu(K_n) \leq n – 2\). On the other hand, let \(x, x + 1\) be the smallest two labels, then the largest label is \(x + n\) and since the graph is complete, the vertices containing these labels form a \(C_3\) subgraph, therefore \[x + x + 1 > x + n,\]
or equivalently, \(x > n – 1\). This establishes that \(\mu(K_n) \geq n – 2\), and therefore \(\mu(K_n) = n – 2\). ◻
Theorem 2. If \(H \in \text{Euclid}(k)\) and \(H \subseteq G\) such that
\(G \setminus H\) is triangular free,
\(|V(G \setminus H)| \geq k\),
then \(G \in \text{Euclid}(0)\).
Proof. Instead of \(NK\), we can use the vertices of \(G\backslash H\) and the result follows. ◻
Definition 3. Let \(v_1, v_2\) be vertices of graphs \(G_1, G_2\), respectively, then the one-point union, \[OU((G_1, \{v_1\}), (G_2, \{v_2\})),\] is the disjoint union \(G_2\) to \(G_1\) then \(v_2\) attaches to \(v_1\).
Example 5. We’ll now look at the Euclid deficiency of one-point union of complete graphs. First, looking at \(OU(K_3, K_n)\) for \(n \geq 3\) we see that \[OU(K_3, K_n) \in \begin{cases} \text{Euclid}(1) & n – 4, \quad 3 \leq n \leq 5 \\ \text{Euclid}(n – 4) & n \geq 6. \end{cases}\] By testing out \(OU(K_4, K_n)\) for \(n \geq 4\), we have that \[OU(K_4, K_n) \in \begin{cases} \text{Euclid}(2) & n – 5, \quad 4 \leq n \leq 7 \\ \text{Euclid}(n – 5) & n \geq 8. \end{cases}\] Testing out similar cases, we see that \[OU(K_5, K_n) \in \begin{cases} \text{Euclid}(3) & n – 6, \quad 5 \leq n \leq 9 \\ \text{Euclid}(n – 6) & n \geq 10, \end{cases}\] \[OU(K_6, K_n) \in \begin{cases} \text{Euclid}(4) & n – 7, \quad 6 \leq n \leq 11 \\ \text{Euclid}(n – 7) & n \geq 12, \end{cases}\] \[OU(K_7, K_n) \in \begin{cases} \text{Euclid}(5) & n – 8, \quad 7 \leq n \leq 13 \\ \text{Euclid}(n – 8) & n \geq 14. \end{cases}\]
In general, we have that
Theorem 3. For \(m \leq n\), \[OU(K_m, K_n) \in \begin{cases} \text{Euclid}(m – 2) & n – m – 1, \quad n \leq 2m – 1 \\ \text{Euclid}(n – m – 1) & n \geq 2m. \end{cases}\]
Proof. Let \(G = OU(K_m, K_n)\) and \(a = \mu(G)\). We’ll label the vertices on \(K_m\) with \(a + 1, a + 2, \ldots, a + m\) with \(a + m\) at the common vertex, and \(a + m, a + m + 1, \ldots, a + m + n – 1\) on the \(K_n\) graph.
If \(n \leq 2m – 1\) then from the subgraph \(K_m\) consisting of \(a + 1, a + 2, a + m\), we have that \[a + 1 + a + 2 > a + m\] or \(a \geq m – 2\). Direct calculation of with \(a = m – 2\) on the \(C_3\) subgraphs of \(G\) consisting of the smallest, second smallest and largest labels in \(K_n\) and \(K_m\) respectively: \[a + 1 + a + 2 = 2m – 1 > 2m – 2 = a + m\] and \[a + m + a + m + 1 = 4m – 3 = (2m – 1) + (2m – 2) \geq n + a + m > a + m + n – 1,\] shows that \(\mu(G) = m – 2\).
If \(n \geq 2m\) then from the subgraph of \(K_n\) consisting of \(a + m, a + m + 1, a + m + n – 1\), we have that \[a + m + a + m + 1 > a + m + n – 1,\] or equivalently \(a \geq n – m – 1\). Direct calculation of with \(a = n – m – 1\) on the \(C_3\) subgraphs of \(G\) consisting of the smallest, second smallest and largest labels in \(K_n\) and \(K_m\) respectively: \[a + 1 + a + 2 = 2n – 2m + 1 \geq n + 1 > n – 1 = a + m\] and \[a + m + a + m + 1 = 2n – 1 > 2n – 2 = a + m + n – 1,\] shows that \(\mu(G) = n – m – 1\). ◻
Definition 4. Let \(e_1, e_2\) be edges of graphs \(G_1, G_2\), respectively, then the one-edge union, \[OE((G_1, \{v_1\}), (G_2, \{v_2\})),\] is the disjoint union \(G_2\) to \(G_1\) then collapse \(e_2\) to \(e_1\).
This construction is dual of one-point union of graphs.
Example 6. \[OE((C_3, (c_1, c_2)), (C_4, (v_1, v_2))).\]
We’ll now look at the Euclid deficiency of one-edge union of complete graphs. First, looking at \(OE(K_3, K_n)\) for \(n \geq 3\) we see that \[OE(K_3, K_3) \in \text{Euclid}(1)\] \[OE(K_3, K_5) \in \text{Euclid}(2)\] or in general, \[OE(K_3, K_4) \in \text{Euclid}(1)\] \[OE(K_3, K_6) \in \text{Euclid}(3)\] \[OE(K_3, K_n) \in \begin{cases} \text{Euclid}(1) & 3 \leq n \leq 4 \\ \text{Euclid}(n – 3) & n \geq 5. \end{cases}\] By testing out \(OE(K_4, K_n)\) for \(n \geq 4\), we have that \[OE(K_4, K_4) \in \text{Euclid}(2)\] \[OE(K_4, K_6) \in \text{Euclid}(2)\] or in general, \[OE(K_4, K_5) \in \text{Euclid}(2)\] \[OE(K_4, K_7) \in \text{Euclid}(3)\] \[OE(K_4, K_n) \in \begin{cases} \text{Euclid}(2) & 4 \leq n \leq 6 \\ \text{Euclid}(n – 4) & n \geq 7. \end{cases}\] Testing out similar cases, we see that \[OE(K_5, K_n) \in \begin{cases} \text{Euclid}(3) & 5 \leq n \leq 8 \\ \text{Euclid}(n – 5) & n \geq 9, \end{cases}\] \[OE(K_6, K_n) \in \begin{cases} \text{Euclid}(4) & 6 \leq n \leq 10 \\ \text{Euclid}(n – 6) & n \geq 12, \end{cases}\] \[OE(K_7, K_n) \in \begin{cases} \text{Euclid}(5) & 7 \leq n \leq 12 \\ \text{Euclid}(n – 7) & n \geq 13. \end{cases}\]
In general, we have that
Theorem 4. For \(m \leq n\), \[OU(K_m, K_n) \in \begin{cases} \text{Euclid}(m – 2) & n \leq 2m – 2 \\ \text{Euclid}(n – m) & n \geq 2m – 1. \end{cases}\]
Proof. The proof is similar to that of Theorem 3. ◻
We appreciate Prof. Harris Kwong for his critical and helpful suggestions on this paper.
The author declares no conflict of interest.