On Vertex Euclidean Deficiency of One-Point Union and One-Edge Union of Complete Graphs

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

Keywords: Euclidean Deficiency, Complete graph

1. Introduction

Definition 1. A $(p, g)$ -graph $G$ is Euclidean if there exists a bijection $f : V \to {1, 2, \dots, 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 $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, \dots, 6$

An immediate observation is that $C_{3}$ is not Euclidean, for the vertices will be labeled with $1, 2, 3$ , but $1 + 2 ≯ 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 ≯ 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 Euclid (0)}$ , where $N_{k}$ is the null graph with $k$ vertices, and we’ll denote this number by $μ (G)$ . For a given $k > 0$ , let $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 $μ (K_{n}) = n - 2$ .

Proof. Observe letting the vertices having labels $n - 1, n, \dots, 2 n - 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 = 2 n - 1,$ greater than all other labels. This establishes that $μ (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 $μ (K_{n}) \geq n - 2$ , and therefore $μ (K_{n}) = n - 2$ .

Theorem 2. If $H \in Euclid (k)$ and $H \subseteq G$ such that

$G ∖ H$ is triangular free,
$| V (G ∖ H) | \geq k$ ,

then $G \in Euclid (0)$ .

Proof. Instead of $N K$ , we can use the vertices of $G ∖ H$ and the result follows.

2. Construction of graphs

Definition 3. Let $v_{1}, v_{2}$ be vertices of graphs $G_{1}, G_{2}$ , respectively, then the one-point union, $O U ((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 $O U (K_{3}, K_{n})$ for $n \geq 3$ we see that $O U (K_{3}, K_{n}) \in {\begin{cases} Euclid (1) & n - 4, 3 \leq n \leq 5 \\ Euclid (n - 4) & n \geq 6. \end{cases}$ By testing out $O U (K_{4}, K_{n})$ for $n \geq 4$ , we have that $O U (K_{4}, K_{n}) \in {\begin{cases} Euclid (2) & n - 5, 4 \leq n \leq 7 \\ Euclid (n - 5) & n \geq 8. \end{cases}$ Testing out similar cases, we see that $O U (K_{5}, K_{n}) \in {\begin{cases} Euclid (3) & n - 6, 5 \leq n \leq 9 \\ Euclid (n - 6) & n \geq 10, \end{cases}$ $O U (K_{6}, K_{n}) \in {\begin{cases} Euclid (4) & n - 7, 6 \leq n \leq 11 \\ Euclid (n - 7) & n \geq 12, \end{cases}$ $O U (K_{7}, K_{n}) \in {\begin{cases} Euclid (5) & n - 8, 7 \leq n \leq 13 \\ Euclid (n - 8) & n \geq 14. \end{cases}$

In general, we have that

Theorem 3. For $m \leq n$ , $O U (K_{m}, K_{n}) \in {\begin{cases} Euclid (m - 2) & n - m - 1, n \leq 2 m - 1 \\ Euclid (n - m - 1) & n \geq 2 m . \end{cases}$

Proof. Let $G = O U (K_{m}, K_{n})$ and $a = μ (G)$ . We’ll label the vertices on $K_{m}$ with $a + 1, a + 2, \dots, a + m$ with $a + m$ at the common vertex, and $a + m, a + m + 1, \dots, a + m + n - 1$ on the $K_{n}$ graph.

If $n \leq 2 m - 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 = 2 m - 1 > 2 m - 2 = a + m$ and $a + m + a + m + 1 = 4 m - 3 = (2 m - 1) + (2 m - 2) \geq n + a + m > a + m + n - 1,$ shows that $μ (G) = m - 2$ .

If $n \geq 2 m$ 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 = 2 n - 2 m + 1 \geq n + 1 > n - 1 = a + m$ and $a + m + a + m + 1 = 2 n - 1 > 2 n - 2 = a + m + n - 1,$ shows that $μ (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, $O E ((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. $O E ((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 $O E (K_{3}, K_{n})$ for $n \geq 3$ we see that $O E (K_{3}, K_{3}) \in Euclid (1)$ $O E (K_{3}, K_{5}) \in Euclid (2)$ or in general, $O E (K_{3}, K_{4}) \in Euclid (1)$ $O E (K_{3}, K_{6}) \in Euclid (3)$ $O E (K_{3}, K_{n}) \in {\begin{cases} Euclid (1) & 3 \leq n \leq 4 \\ Euclid (n - 3) & n \geq 5. \end{cases}$ By testing out $O E (K_{4}, K_{n})$ for $n \geq 4$ , we have that $O E (K_{4}, K_{4}) \in Euclid (2)$ $O E (K_{4}, K_{6}) \in Euclid (2)$ or in general, $O E (K_{4}, K_{5}) \in Euclid (2)$ $O E (K_{4}, K_{7}) \in Euclid (3)$ $O E (K_{4}, K_{n}) \in {\begin{cases} Euclid (2) & 4 \leq n \leq 6 \\ Euclid (n - 4) & n \geq 7. \end{cases}$ Testing out similar cases, we see that $O E (K_{5}, K_{n}) \in {\begin{cases} Euclid (3) & 5 \leq n \leq 8 \\ Euclid (n - 5) & n \geq 9, \end{cases}$ $O E (K_{6}, K_{n}) \in {\begin{cases} Euclid (4) & 6 \leq n \leq 10 \\ Euclid (n - 6) & n \geq 12, \end{cases}$ $O E (K_{7}, K_{n}) \in {\begin{cases} Euclid (5) & 7 \leq n \leq 12 \\ Euclid (n - 7) & n \geq 13. \end{cases}$

In general, we have that

Theorem 4. For $m \leq n$ , $O U (K_{m}, K_{n}) \in {\begin{cases} Euclid (m - 2) & n \leq 2 m - 2 \\ Euclid (n - m) & n \geq 2 m - 1. \end{cases}$

Proof. The proof is similar to that of Theorem 3.

Acknowledgment

We appreciate Prof. Harris Kwong for his critical and helpful suggestions on this paper.

Conflict of interest

The author declares no conflict of interest.

References:

Gallian, J. A., 2017. A dynamic survey of graph labeling. Electronic Journal of Combinatorics, 20(DS6), pp.1-30.
Harary, F., 1969. Graph theory. Reading, MA: Addison-Wesley.
Lee, S. M., n.d.. On vertex Euclidean graphs. (Manuscript)
Shee, S. C. and Ho, Y. S., 1993. The cordiality of one-point union of copies of graphs. Discrete Mathematics, 117, pp.225-243.

[1] Gallian, J. A., 2017. A dynamic survey of graph labeling. Electronic Journal of Combinatorics, 20(DS6), pp.1-30.

[2] Harary, F., 1969. Graph theory. Reading, MA: Addison-Wesley.

[3] Lee, S. M., n.d.. On vertex Euclidean graphs. (Manuscript)

[4] Shee, S. C. and Ho, Y. S., 1993. The cordiality of one-point union of copies of graphs. Discrete Mathematics, 117, pp.225-243.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

On Vertex Euclidean Deficiency of One-Point Union and One-Edge Union of Complete Graphs

Abstract

1. Introduction

2. Construction of graphs

Acknowledgment

Conflict of interest

References:

Information

Guidelines

CP Initiatives

Follow CP