### Orthogonal embeddings of graphs in Euclidean space

#### Abstract

Let *G* = (*V*, *E*) be a simple connected graph. An injective function *f* : *V* → *R*^{n} is called an *n*-dimensional (or *n*-D) orthogonal labeling of *G* if *u**v*, *u**w* ∈ *E* implies that (*f*(*v*) − *f*(*u*)) ⋅ (*f*(*w*) − *f*(*u*)) = 0, where ⋅ is the usual dot product in Euclidean space. If such an orthogonal labeling *f* of *G* exists, then *G* is said to be embedded in *R*^{n} orthogonally. Let the orthogonal rank *o**r*(*G*) of *G* be the minimum value of *n*, where *G* admits an *n*-D orthogonal labeling (otherwise, we define *o**r*(*G*) = ∞). In this paper, we establish some general results for orthogonal embeddings of graphs. We also determine the orthogonal ranks for cycles, complete bipartite graphs, one-point union of two graphs, Cartesian product of orthogonal graphs, bicyclic graphs without pendant, and tessellation graphs.

#### Keywords

#### Full Text:

PDFDOI: http://dx.doi.org/10.5614/ejgta.2019.7.2.13

#### References

J.A. Bondy and U.S.R. Murty. Graph Theory with Applications, MacMillan, New York, (1976).

J.A. Gallian. A dynamic survey of graph labeling, Electron. J. Combin. 20 (2017), #DS6. [3] B. Immanuel and K.A. Sugeng. Orthogonal labeling, Indonesian Journal of Combinatorics. 1 (2016), 1-8.

W.C. Shiu and P.C.B. Lam. The Wiener number of the hexagonal net, Discrete Appl. Math. 73 (1997), 101-111.

W.C. Shiu and P.C.B. Lam. Wiener numbers of pericondensed benzenoid molecule systems, Congr. Numer. 126 (1997), 113-124.

W.C. Shiu and R.M. Low. The integer-magic spectra of bicyclic graphs without pendant, Congr. Numer. 214 (2012), 65-73.

### Refbacks

- There are currently no refbacks.

ISSN: 2338-2287

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.