Search

We give a new method of generating strongly polynomial sequences of graphs, i.e., sequences ( H k ) indexed by a tuple k = ( k 1 , … , k h ) of positive integers, with the property that, for each fixed graph G , there is a multivariate polynomial p ( G ; x 1 , … , x h ) such that the number of homomorphisms from G to H k is given by the evaluation p ( G ; k 1 , … , k h ) . A classical example is the sequence of complete graphs ( K k ) , for which p ( G ; x ) is the chromatic polynomial of G . Our construction is based on tree model representations of graphs. It produces a large family of graph polynomials which includes the Tutte polynomial, the Averbouch–Godlin–Makowsky polynomial, and the Tittmann–Averbouch–Makowsky polynomial. We also introduce a new graph parameter, the branching core size of a simple graph, derived from its representation under a particular tree model, and related to how many involutive automorphisms it has. We prove that a countable family of graphs of bounded branching core size is always contained in the union of a finite number of strongly polynomial sequences. [ABSTRACT FROM AUTHOR]

The number of homomorphisms from a finite graph F to the complete graph K n is the evaluation of the chromatic polynomial of F at n . Suitably scaled, this is the Tutte polynomial evaluation T ( F ; 1 − n , 0 ) and an invariant of the cycle matroid of F . De la Harpe and Jaeger [8] asked more generally when is it the case that a graph parameter obtained from counting homomorphisms from F to a fixed graph G depends only on the cycle matroid of F . They showed that this is true when G has a generously transitive automorphism group (examples include Cayley graphs on an abelian group, and Kneser graphs). Using tools from multilinear algebra, we prove the converse statement, thus characterizing finite graphs G for which counting homomorphisms to G yields a matroid invariant. We also extend this result to finite weighted graphs G (where to count homomorphisms from F to G includes such problems as counting nowhere-zero flows of F and evaluating the partition function of an interaction model on F ). [ABSTRACT FROM AUTHOR]

Abstract: The primary endpoint of signalling through the canonical Raf–MEK–ERK MAP kinase cascade is ERK activation. Here we report a novel signalling outcome for this pathway. Activation of the MAP kinase pathway by growth factors or phorbol esters during G2 phase results in only transient activations of ERK and p90RSK, then suppression to below control levels. A small peak of ERK and p90RSK activation in early G2 phase cells was identified, and inhibition of this delayed entry into mitosis. The previously identified, proteolytically cleaved form of MEK1 termed tMEK (truncated MEK1), is also induced with G2 phase MAPK pathway activation. We demonstrate that addition of recombinant mutants of MEK1 with an N-terminal truncation similar to that of tMEK also inhibited ERK and p90RSK activations and delayed progression into mitosis. Only catalytically inactive forms of tMEK were capable of these effects, but surprisingly, phosphorylation on the activating Ser218/222 sites was also required. A lack of MEK1 or ability to accumulate tMEK resulted in the absence of the feedback inhibition of ERK and p90RSK activations. tMEK is a novel output from the canonical MAP kinase signalling pathway, acting in a MAPK signalling-regulated dominant negative manner to inhibit ERK and p90RSK activations, acting as a dampening mechanism to reduce the magnitude or duration of MAPK pathway signalling in G2/M phase. [Copyright &y& Elsevier]

The spatial organization of Ras proteins into nanoclusters on the inner leaflet of the plasma membrane is essential for high fidelity signaling through the MAPK pathway. Here we identify two selective regulators of K-Ras nanoclustering from a proteomic screen for K-Ras interacting proteins. Nucleophosmin (NPM) and nucleolin are predominantly localized to the nucleolus but also have extranuclear functions. We show that a subset of NPM and nucleolin localizes to the inner leaflet of plasma membrane and forms specific complexes with K-Ras but not other Ras isoforms. Active GTPloaded and inactive GDP-loaded K-Ras both interact with NPM, although NPM-K-Ras binding is increased by growth factor receptor activation. NPM and nucleolin both stabilize K-Ras levels on the plasma membrane, but NPM concurrently increases the clustered fraction of GTP-K-Ras. The increase in nanoclustered GTP-K-Ras in turn enhances signal gain in the MAPK pathway. In summary these results reveal novel extranucleolar functions for NPM and nucleolin as regulators of K-Ras nanocluster formation and activation of the MAPK pathway. The study also identifies a new class of K-Ras nanocluster regulator that operates independently of the structural scaffold galectin-3. [ABSTRACT FROM AUTHOR]