Triangulated graphs have many interesting properties (perfection, recognition algorithms, combinatorial optimization algorithms with linear complexity). Hyper-triangulated graphs are those where each induced subgraph has a hyper-simplicial vertex. In this paper we give the characterizations of hyper-triangulated graphs using an ordering of vertices and the weak decomposition. We also offer a recognition algorithm for the hyper-triangulated graphs, the inclusions between the triangulated graphs generalizations and we show that any hyper-triangulated graph is perfect.

Additional Information

Author(s)

 Talmaciu, Mihai

DOI

https://doi.org/10.37193/CJM.2021.01.12