A connected partition of a graph G is a partition of its vertex set such that each induced subgraph is connected. In earlier research it was called a connected composition of a graph. We find a polynomial, the defect polynomial of the graph, that decribes the number of connected partitions of complements of graphs with respect to any complete graph. The defect polynomial is calculated for several classes of graphs as cycles or matchings.
展开▼
