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 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 ∪ N k is Euclidean. We study the Euclidean Deficiency of one-point union and one-edge union of complete graphs.