Recognizing hinge-free line graphs and total graphs

In this paper, we characterize line graphs and total graphs that are hinge-free, i.e., there is no triple of vertices x,y,z such that the distance between y and z increases after x is removed. Based on our characterizations, we show that given a graph G with n vertices and m edges, determining its line graph and total graph to be hinge-free can be solved in O(n + m) time. Moreover, characterizations of hinge-free iterated line graphs and total graphs are also discussed.