Recognizing the \(P_ 4\)-structures of a tree (Q1343225)

The \(P_ 4\)-structure of a graph \(G\) is the hypergraph having the same set of vertices as \(G\) and those 4-sets as hyperedges whose induced subgraph of \(G\) is a path. The paper presents a polynomial time algorithm detecting whether a given 4-uniform hypergraph is the \(P_ 4\)-structure of a tree, which is given in that case, or not. Non-isomorphic trees of the same order have the same \(P_ 4\)-struture iff both belong to a class of trees described in the paper.