Simplicial decompositions of graphs - some uniqueness results (Q1068851)

A simplicial decomposition of a graph G is the recursively defined analog to writing G as the union of two proper subgraphs overlapping in a complete graph (a 'simplex'). We consider simplicial decompositions into primes, i.e. into graphs that cannot be decomposed further in this way. Such decompositions can be used for characterizing suitable graph properties \({\mathfrak G}\) by giving a list B of possible primes of their members \(G\in {\mathfrak G}\), together with an explicit rule stating how exactly one must assemble the elements of B to obtain the members of \({\mathfrak G}\). For such characterizations results are needed asserting the independence of the factors as well as of the 'simplices of attachment' from the decomposition chosen. We prove such uniqueness results by characterizing both prime factors and simplices of attachment without reference to any particular decomposition. The paper is self-contained, and its first part can also be read as a general but brief introduction to the theory of simplicial decompositions as such.