Abstract
L. Lovasz introduced k-connection matrices (aka Hankel matrices of k-connections) for graph properties and numeric graph parameters p. The Hankel rank R(k,p) of a graph parameter p with respect to k-connections is the rank of the corresponding k-connection matrix. Theorem 1: A graph parameter p of finite Hankel rank R(k,p) can be computed in polynomial time on graphs of tree-width at most k (L. Lovasz). Theorem 2: Every graph parameter p definable in Monadic Second Order Logic with modular counting (CMSOL) has finite rank R(k,p) (B. Godlin, T. Kotek and J. Makowsky). Instead of k-connections other sumlike opertaions G * H on graphs can be considered. R(*,p) denotes the rank of the Hankel matrix of p with respect to *. Showing that R(*,p) is infinite can be used to show that p is not CMSOL definable (T. Kotek and J. Makowsky). In this talk we discuss extensions of the above theorems in two directions: We replace k-connections by various operations * and 1. prove an analogous results for graph classes of bounded clique-width; 2. discuss how to construct possible extensions L of CMSOL for which all L-definable graph properties p have finite rank R(*,p) for all sum-like operations. (Joint work with N. Labai)