I am studying a paper, and there is a definition for a total graph. It states

The total graph $T(G)$ of a graph $G$ is the graph whose vertices correspond to the vertices and edges of $G$, and whose two vertices are joint if and only if the corresponding vertices are adjacent, edges are adjacent or vertices and edges are incident in $G$.

I am having trouble understanding some parts of it.

  1. How can vertices correspond to the edges like it states in the first part.

  2. What edges does it mean when it insists them to be adjacent, or incident.



An example should help.

Think about the triangle as a graph with three vertices $A, B, C$ and three edges $(AB), (BC), (AC)$. Then the total graph of $G$ has six vertices: $$ A, B, C, (AB), (BC), (AC) . $$ Its edges are the pairs of vertices $$ (AB), (BC), (AC) $$ (corresponding to adjacent vertices of $G$), $$ ((AB)(AC)), ((AB)(BC)), ((AC)(BC)) $$ (corresponding to edges that share a vertex) and edges like $$ (A, (AB)) $$ (corresponding to vertices on edges).

  • $\begingroup$ Thank you very much. $\endgroup$ – Vahe Karamyan Aug 6 at 16:24

The vertices of a graph can be any objects. In this cases the vertices of $T(G)$ are the vertices and edges of $G$. Now we have to define adjacency in $T(G)$. Two vertices in $T(G)$ correspond either to

  1. Two vertices of $G$
  2. Two edges of $G$
  3. A vertex of $G$ and an edge of $G$

The definition gives the conditions under which these are adjacent.

For example if G=C_3 then T(G)=K_6.

  • $\begingroup$ Thanks, got it. $\endgroup$ – Vahe Karamyan Aug 6 at 16:24
  • $\begingroup$ @VaheKaramyan I just realized my example was wrong, but since you've figured things out, I won't bother to correct it. $\endgroup$ – saulspatz Aug 6 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.