Find in Library

<p>Let <span class="math"><em>G</em> = (<em>V</em>, <em>E</em>)</span> be a simple connected graph. An injective function <span class="math"><em>f</em> : <em>V</em> → <em>R</em>^<em>n</em></span> is called an <span class="math"><em>n</em></span>-dimensional (or <span class="math"><em>n</em></span>-D) orthogonal labeling of <span class="math"><em>G</em></span> if <span class="math"><em>u</em><em>v</em>, <em>u</em><em>w</em> ∈ <em>E</em></span> implies that <span class="math">(<em>f</em>(<em>v</em>) − <em>f</em>(<em>u</em>)) ⋅ (<em>f</em>(<em>w</em>) − <em>f</em>(<em>u</em>)) = 0</span>, where <span class="math"> ⋅ </span> is the usual dot product in Euclidean space. If such an orthogonal labeling <span class="math"><em>f</em></span> of <span class="math"><em>G</em></span> exists, then <span class="math"><em>G</em></span> is said to be embedded in <span class="math"><em>R</em>^<em>n</em></span> orthogonally. Let the orthogonal rank <span class="math"><em>o</em><em>r</em>(<em>G</em>)</span> of <span class="math"><em>G</em></span> be the minimum value of <span class="math"><em>n</em></span>, where <span class="math"><em>G</em></span> admits an <span class="math"><em>n</em></span>-D orthogonal labeling (otherwise, we define <span class="math"><em>o</em><em>r</em>(<em>G</em>) = ∞</span>). 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.</p>