Orthogonal labeling

Let ∆G be the maximum degree of a simple connected graph G(V,E). An injective mapping P : V → RG is said to be an orthogonal labeling of G if uv, uw ∈ E implies (P (v) − P (u)) · (P (w) − P (u)) = 0, where · is the usual dot product defined in Euclidean space. A graph G which has an orthogonal labeling is called an orthogonal graph. This labeling is motivated by the existence of some labelings defined on some algebraic structure, i.e. harmonious labeling and group distance magic labeling. In this paper we study some preliminary results on orthogonal labeling. One of the early results is the fact that cycles with even number of vertices are orthogonal, while cycles with odd number of vertices are not. The main results in this paper state that any graph containingK3 as a subgraph is non-orthogonal and that a graphG′ obtained from adding a pendant to a vertex in an orthogonal graph G is orthogonal. Moreover, we show that any tree is orthogonal.