Graph theory notation of path concatenation I was wondering what the proper notation would be when concatenating paths, written as a sequence of nodes, rather than a set of edges.
That is:
Given:
$$
    P = ( x, y, z )
$$
Is it valid to write the following path concatenations? 
$$
\begin{eqnarray}
P' & = & ( s, x, y, z, t ) \\
& = & ( s, P, t ) \\
& = & ( s ) \cup P \cup ( t ) \\
& = & ( s ) + P + ( t )
\end{eqnarray}
$$
I'm assuming not all of them are regarded as valid.
So which one is preferable? Or am I overlooking a better notation?
I would prefer not having to fallback to the more verbose:
$$
\begin{eqnarray}
P &=& \{(x,y), (y,z)\} \\
P'&=& \{( s, x ), (x, y), (y,z), (z,t)\} \\
  &=& \{(s,x),(z,t)\} \cup P
\end{eqnarray}
$$
However, I would still like to be able to reason about the edges along the path $P$ and $P'$, e.g.:
$$
(x,y) \in P
$$
or write itterations over edges in P:
$$
\{ \text{do something with $v$ and/or $w$...} \; | \; ( v, w ) \in P \}
$$
 A: I suggest that you pick something reasonable and unambiguous, state it clearly, and then stick with it.  Do not use $\cup$, since that means set union. 
For example, you might use a semicolon: $P_1;P_2$ means that $P_1$ ends at the same vertex at which $P_2$ starts, and we want the path that traces $P_1$ and then $P_2$.   This expands nicely to include extra vertices: $P_1;v;P_2$ means the path that goes along $P_1$, then from the end vertex of $P_1$ to $v$, then to the start vertex of $P_2$, and so on.  This notation requires that we understand the $v$ by itself as a trivial path with no edges, which is quite reasonable.  Similarly $s;P;t$ is a straightforward extension of the notation.
Usually paths are sequences of edges, not sets of edges; the order of the edges in the path is important.  I would avoid writing $P = \{(a,b), (b,c)\}$ for this reason, preferring something like $P = \langle a,b,c\rangle$ if there is at most one edge between any pair of vertices, or $P=a\stackrel{E_1}{\to}b\stackrel{E_2}{\to}c$ otherwise or if the names of the edges are important.
You could say that you will abuse notation by writing $E_1\in P$ when you mean that $E_1$ is one of the edges in the path $P$, and this probably won't bother anyone.  If it worries you, you might say that you will use $\lvert P\rvert$ to mean the set of edges in $P$, and then $E_1\in\lvert P\rvert$ and $\{\text{do something with $v$ and/or $w\ldots$} \mid (v,w)\in\lvert P\rvert\}$ are completely reasonable and also easy to understand.
You might also take a look at some elementary graph algorithm books to see what they do in similar cases.
A: In topology, a path is a function from an interval to a specified topological space, and the composition of two paths $f$ and $g$ is often just denoted $fg$.
In formal languages, a string is a sequence of characters from a specified alphabet, and the concatenation of two strings $\sigma_1$ and $\sigma_2$ is denoted $\sigma_1\sigma_2$.
Paths in a graph are closely analogous both to topological paths and to sequences of nodes/edges, which suggests denoting path concatenation simply as juxtaposition. In particular, I would write the path in your question simply as $sPt$, or as $e_1Pe_2$ where $e_1$ and $e_2$ join $s$ to $x$ and $z$ to $t$ respectively.
A: It depends. If your paths are simple (i.e. no vertex can appear twice), then the usual set operations should be enough.
If you can have arbitrarily complex paths, then consider the following solutions:


*

*Define a new operator for path concatenation, for example $\circ$ or $\oplus$, and then use it like $\langle s \rangle \circ P \circ \langle t \rangle$, remember to differentiate between sets of nodes and paths, e.g. by using $\{$ braces $\}$ and $\langle$ brackets $\rangle$.

*Use notation from rewriting systems, where usually a single edge is denoted by $\alpha \to \beta$ or $\alpha \leadsto \beta$, while multiple edges get a star (or a plus $+$ if there is at least one edge), $\alpha \to^* \beta$ or $\alpha \leadsto^* \beta$. Of course, if you need you can label edges $\alpha \xrightarrow{e_{\alpha\beta}} \beta$ or entire paths $\alpha \xrightarrow{P}{\!\!}^* \beta$. If you were to use this one, I recommend \xrightarrow{text} instead of \stackrel{text}{\to}.


Have fun ;-)
