Total Graphs and Traversability

Source abstract

With every graph G (finite and undirected with no loops or multiple lines) there is associated a graph L ( G ), called the line-graph of G , whose points correspond in a one-to-one manner with the lines of G in such a way that two points of L ( G ) are adjacent if and only if the corresponding lines of G are adjacent. This concept was originated by Whitney ( 3 ). In a similar way one can associate with G another graph which we call its total graph and denote by T ( G ). This new graph has the property that a one-to-one correspondence can be established between its points and the elements (the set of points and lines) of G such that two points of T ( G ) are adjacent if and only if the corresponding elements of G are adjacent (if both elements are points or both are lines) or theyare incident