The lattice polynomial of a graph. (Q2715980)

The authors associate with a finite simple graph \(G\) the polynomial (which they call lattice polynomial) \(\pi (G,t)=\sum \mu (H)t^{| H| }\) where the summation goes over the poset \(P\) of connected induced subgraphs of \(G\) (ordered by inclusion), \(\mu \) is the Möbius function of \(P\), and \(| H| \) is the number of vertices in \(H\). The behaviour of the lattice polynomial with respect to various graph operations (disjoint union, join, \(K_n\)-amalgamation, edge deletion) is studied and lattice polynomials of several classes of graphs (trees, maximal outerplanar graphs, \(K_{m,n}\), \(C_n\)) are determined.