Geodesic convexity in labeled graphs

Abstract

This paper is an attempt to study geodesic convexity in a graph $G$ with respect to a labeling function $\mathscr{L}$ defined on the vertex set of $G$. Let $G(V, E)$ be an undirected, connected graph without loops and multiple edges. A bijective function $\mathscr{L}: V(G) \rightarrow\{1,2,3, \ldots,|V(G)|\}$ be a vertex labeling of $G$ and it induces a function $\mathscr{L}^*: E(G) \rightarrow\{1,2,3, \ldots,|V(G)|\}$ defined by $\mathscr{L}^*(u v)=|\mathscr{L}(u)-\mathscr{L}(v)|$. Let $\Gamma_{\mathscr{L}}=(G, \mathscr{L})$ be a labeled graph. An $\mathscr{L}_g$ convexity space is an ordered pair $\left(\Gamma_{\mathscr{L}}, \mathscr{C}_{\mathscr{L}}\right)$ where, $\Gamma_{\mathscr{L}}$ is a labeled graph and $\mathscr{C}_{\mathscr{L}}$ is the convexity induced by the label $\mathscr{L}$. The function $\mathscr{L}$ is called a geodesic convex label or simply $g$ - convex label if the convexity $\mathscr{C}_{\mathscr{L}}$ induced by the label $\mathscr{L}$ coincides with the geodesic convexity $\mathscr{C}$ on $V$. A graph $G$ is defined to be a geodesically elegant graph if there exist a $g$-convex label for $G$.