In graph theory, a tortoise graph $T_n$ is a specific type of graph derived from a path graph, subject to certain conditions on the number of vertices.
Based on the provided reference, the tortoise graph $T_n$ is defined as follows:
The tortoise graph $T_n$ is the graph obtained from a path $P_n$, where $n$ is an odd integer, by attaching an edge between vertex $vi$ and vertex $v{n−i+1}$ for each value of $i$ from $1$ up to $\lfloor n/2 \rfloor$.
Construction of a Tortoise Graph $T_n$
To understand how a tortoise graph $T_n$ is formed, consider these steps:
- Start with a Path Graph $P_n$: Begin with a simple path graph containing $n$ vertices, labeled $v_1, v_2, \ldots, v_n$. The path graph $P_n$ has edges connecting $vi$ to $v{i+1}$ for $1 \le i \le n-1$.
- Condition on $n$: The number of vertices, $n$, must be an odd integer.
- Add New Edges: Additional edges are added to this path graph. For each integer $i$ starting from $1$ up to $\lfloor n/2 \rfloor$, an edge is created connecting the vertex $vi$ and the vertex $v{n-i+1}$.
This means edges are added between:
- $v_1$ and $v_n$
- $v2$ and $v{n-1}$
- $v3$ and $v{n-2}$
- ... and so on, until $i$ reaches $\lfloor n/2 \rfloor$.
Properties of $T_n$
The vertex set of the tortoise graph $T_n$ is the same as the vertex set of the original path graph $P_n$, i.e., $V(T_n) = V(P_n)$. The edge set of $T_n$ consists of the edges from $P_n$ combined with the newly added edges. The reference notes that the edge set is $E(T_n) = E(P_n) \cup {e_i = vi v{n−i+1}, i = n, n − 1, \ldots, (n + 3/2)}$. (Note: The indexing notation for the added edges $e_i$ as $i = n, n-1, \dots, (n+3/2)$ in the reference seems related to specific edge labeling context, while the vertex connection rule $vi v{n-i+1}$ for $1 \le i \le \lfloor n/2 \rfloor$ defines which edges are added).
A significant property mentioned in the reference is:
- The tortoise graph $T_n$ has a 2-edge even graceful labeling.
In essence, the tortoise graph takes a linear path of an odd number of vertices and adds chords that symmetrically connect vertices from the beginning of the path to corresponding vertices from the end of the path.
