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 → 1, 2, …, p such that for any induced C 3 -subgraph v 1, v 2, v 3 in G with f (v 1) f (v 3). The Euclidean Deficiency of a graph G is the smallest integer k such that G ∪ N k is Euclidean. We study the Euclidean Deficiency of one-point union and one-edge union of complete graphs.