On Vertex-Euclidean Deficiency of Complete Fan Graphs and Complete Wheel Graphs

A simple graph $G$ with $p$ vertices is said to be vertex-Euclidean if there exists a bijection $f : V (G) \to {1, 2, \dots, 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.

Keywords: Graph labeling, Wheel graph, Fan graph

1. Introduction

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) \to {1, 2, \dots, 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 $μ_{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 $μ_{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 $μ_{e} (G)$ as the smallest integer $k$ such that $G$ admits a bijection edge labeling $f : E (G) \to {k + 1, k + 2, \dots, 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) \to {1, 2, \dots, 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 ≯ 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 ≯ 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 $μ_{v} (G) = k$ .

For example, a graph $G$ is vertex-Euclidean if and only if $μ_{v} (G) = 0$ . It is easy to see that $μ_{v} (C_{3}) = 1$ .

We also find $μ_{v} (K_{4}) = 2$ . The reason is: if $μ_{v} (K_{4}) = 1$ , then the four vertices of $K_{4}$ will be labeled 2, 3, 4, and 5. Since $2 + 3 ≯ 5$ , this labeling is not vertex-Euclidean. Thus, the smallest label on $K_{4}$ is 3. This shows that $μ_{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 \geq 3$ , we have $μ_{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 $μ_{v} (G) \leq p - 2$ .

Proof. It is clear that if $H$ is a subgraph of $G$ with the same number of vertices, then $μ_{v} (H) \leq μ_{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.

2. Complete Fan Graphs

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 $μ_{v} (F_{n}) = 1$ for all integers $n \geq 2$ . Since each fan graph is triangulated, $μ_{v} (F_{n}) \geq 1$ . 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, $μ_{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 \geq 3$ and $n \geq 2$ , define the complete fan graph $K_{m} F_{n}$ as follows.

Let $V (K_{m} F_{n}) = {c} \cup {v_{1}, v_{2}, \dots, v_{n}} \cup {v_{i, 1}, v_{i, 2}, \dots, v_{i, m - 3} ∣ 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}, \dots, v_{i, m - 3}}$ for $1 \leq i \leq n - 1$ .

Notice that

the vertex set ${c, v_{1}, v_{2}, \dots, 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 $μ_{v} (K_{4} F_{n}) = 2$ .

In general, since $K_{4} F_{n}$ contains at least one copy of $K_{4}$ , we know that $μ_{v} (K_{4} F_{n}) \geq μ_{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 $μ_{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 $μ_{v} (K_{m} F_{n}) = m - 2$ for all integers $m \geq 3$ and $n \geq 2$ .

3. Complete Wheel Graphs

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 \geq 3$ . 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 $μ_{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 $μ_{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 $m b o x v E u c l i d (k)$ for the set of all connected graphs $G$ with $μ_{v} (G) = k$ . We say a graph $G$ is critically vertex-Euclidean if $μ_{v} (G) = k$ , and $μ_{v} (G - v) = k$ for any vertex $v$ in $G$ , and use the notation $vCritEuclid (k)$ , or simply $m b o x {v E u c l i d}^{*} (k)$ to indicate the set of all critically vertex-Euclidean graphs with $μ_{v} (G) = k$ . Obviously, if $G \in vEuclid (0)$ , then we also have $G \in m b o x {v E u c l i d}^{*} (0)$ . It is not obvious that $m b o x {v E u c l i d}^{*} (k) \neq \emptyset$ if $k \neq 0$ . 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 $μ_{v} (C_{3} [N_{3}]) = 5$ :

Due to symmetry, it suffices to study $C_{3} [N_{3}] - v$ for any vertex $v$ :

Since $μ_{v} (C_{3} [N_{3}] - v) = 5$ , we deduce that $C_{3} [N_{3}] \in m b o x {v E u c l i d}^{*} (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 $m b o x {v E u c l i d}^{*} (k ↓ S)$ for the set of all connected graphs $G$ with $μ_{v} (G) = k$ , and $S$ is the minimal set that contains all possible values of $μ_{v} (G - v)$ taken over the vertices $v$ in $G$ . For example, we find $K_{3} F_{3} \in m b o x {v E u c l i d}^{*} (1 ↓ {1, 0})$ :

Here, we use an asterisk to indicated the removed vertex. We also have $K_{3} F_{4} \in m b o x {v E u c l i d}^{*} (1 ↓ {1, 0})$ :

We find $K_{4} F_{3}, K_{4} F_{4} \in m b o x {v E u c l i d}^{*} (2 ↓ {1})$ :

We also find $K_{5} F_{3}, K_{5} F_{5} \in m b o x {v E u c l i d}^{*} (3 ↓ {2})$ :

and $K_{6} F_{4} \in m b o x {v E u c l i d}^{*} (4 ↓ {3})$ :

Conjecture 1. $K_{m} F_{n} \in {\begin{cases} m b o x {v E u c l i d}^{*} (1 ↓ {1, 0}) & if n = 3, \\ m b o x {v E u c l i d}^{*} (n - 2 ↓ {n - 3}) & if n \geq 4. \end{cases}$

The behavior of the complete wheel graphs $K_{m} W_{n}$ is more complex. We find $K_{3} W_{3} \in m b o x {v E u c l i d}^{*} (1)$ :

However, we have $K_{3} W_{4} \in m b o x {v E u c l i d}^{*} (2 ↓ {1, 0})$ :

We also find $K_{3} W_{5} \in m b o x {v E u c l i d}^{*} (2 ↓ {1, 0})$ :

However, we have $K_{3} W_{6} \in m b o x {v E u c l i d}^{*} (3 ↓ {2, 0})$ :

We also find $K_{3} W_{7} \in m b o x {v E u c l i d}^{*} (3 ↓ {2, 0})$ :

However, we have $K_{3} W_{8} \in m b o x {v E u c l i d}^{*} (4 ↓ {3, 0})$ :

Unexpectedly, we find $K_{3} W_{9} \in m b o x {v E u c l i d}^{*} (5 ↓ {4, 0})$ :

The behavior becomes more complex when $m = 4$ . We have found that $μ_{v} (K_{4} W_{3}) = 2$ :

We find $K_{4} W_{3} \in m b o x {v E u c l i d}^{*} (2 ↓ {2, 1})$ :

We know that $μ_{v} (K_{4} W_{4}) = 2$ :

But we have $K_{4} W_{4} \in m b o x {v E u c l i d}^{*} (2 ↓ {3, 2, 1})$ :

What if $m = 5$ ? We know that $μ_{v} (K_{5} W_{4}) = 4$ . We find $K_{5} W_{4} \in m b o x {v E u c l i d}^{*} (4 ↓ {3, 2})$ :

Let us consider yet another example. We know that $μ_{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 m b o x {v E u c l i d}^{*} (4 ↓ {4, 3})$ .

The case of $K_{m} W_{n}$ appears to be rather complex. We invite the readers the study these problems.

5. Research 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 $μ_{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 $μ_{v} (G) < p - 2$ ?
Study the analogous problems for $μ_{e} (G)$ .

Acknowledgment

We are indebted to the anonymous referee, whose comments and suggestions provide valuable insights that lead to the improvement of the manuscript.

Conflict of Interest

The authors declare no conflict of interest.

References:

Harary, F., 1969. Graph theory.
Addison-Wesley. Zykov, A. A., 1949. On some properties of linear complexes. Matematicheskii Sbornik, 66(2), pp.163–188.

[1] Harary, F., 1969. Graph theory.

[2] Addison-Wesley. Zykov, A. A., 1949. On some properties of linear complexes. Matematicheskii Sbornik, 66(2), pp.163–188.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing