We describe all linear operators on spaces of multivariate polynomials preserving the property of being non-vanishing in open circular domains. This completes the multivariate generalization of the ...classification program initiated by Pólya–Schur for univariate real polynomials and provides a natural framework for dealing in a uniform way with Lee–Yang type problems in statistical mechanics, combinatorics, and geometric function theory.
Subgraphs of pair vertices Jäntschi, Lorentz; Diudea, Mircea V.
Journal of mathematical chemistry,
02/2009, Letnik:
45, Številka:
2
Journal Article, Conference Proceeding
Recenzirano
Subgraphs obtained by applying several fragmentation criteria are investigated. Two well known criteria (Szeged and Cluj), and two new others are defined and characterized. An example is given for ...the discussed procedures. The matrix and polynomial representations of vertices composing each type of subgraphs were also given. Analytical formulas for the polynomials of several classes of graphs are derived. The newly introduced subgraphs/fragments, called MaxF and CMaxF, appear to have interesting properties, which are demonstrated.
The Martin polynomials, introduced by Martin in his 1977 thesis, encode information about the families of circuits in Eulerian graphs and digraphs. The circuit partition polynomials,
J(
G;
x) and
j(
...G
→
;x)
, are simple transformations of the Martin polynomials. We give new identities for these polynomials, analogous to Tutte's identity for the chromatic polynomial. Following a useful expansion of Bollobás J. Combin. Theory Ser. B 85 (2002) 261–268, these formulas give combinatorial interpretations for all integer evaluations of the circuit partition and Martin polynomials. Selected evaluations of the formulas give combinatorial identities that expose the structure and relations of Eulerian graphs and digraphs. New identities and combinatorial interpretations for all integer values of the Tutte polynomial of a planar graph along the line
y=
x also follow from these results.
The Martin polynomial of an oriented Eulerian graph encodes information about families of cycles in the graph. This paper uses a transformation of the Martin polynomial that facilitates standard ...combinatorial manipulations. These manipulations result in several new identities for the Martin polynomial, including a differentiation formula. These identities are then applied to get new combinatorial interpretations for valuations of the Martin polynomial, revealing properties of oriented Eulerian graphs. Furthermore, Martin (Thesis, Grenoble, 1977; J. Combin. Theory, Ser. B 24 (1978) 318) and Las Vergnas (Graph Theory and Combinatorics, Research Notes in Mathematics, Vol. 34, Pitman, Boston, 1979; J. Combin. Theory, Ser. B 44 (1988) 367), discovered that if
G
m
, the medial graph of a connected planar graph
G, is given an appropriate orientation, then
m(
G
→
m;x)=t(G;x,x)
, where
m(
G
→
;x)
is the Martin polynomial of an oriented graph, and
t(
G;
x,
y) is the Tutte, or dichromatic, polynomial. This relationship, combined with the new evaluations of the Martin polynomial, reveals some surprising properties of the Tutte polynomial of a planar graph along the diagonal
x=
y. For small values of
x and
y that correspond to points where interpretations of the Tutte polynomial are known, this leads to some interesting combinatorial identities, including a new interpretation for the beta invariant of a planar graph. Combinatorial interpretations for some values of the derivatives of
t(
G;
x,
x) for a planar graph
G are also found.
We consider various classes of graph polynomials and study their computational complexity. Our main focus is on Farrell polynomials and generating functions of graph properties. All these polynomials ...have a wide range of applications in combinatorics, but also in physics, chemistry, and biology. In general, the worst-case complexity of most these polynomials is known to be
NP-hard, or even
♯
P
-hard. We show that, if these polynomials satisfy a definability condition in the formalisms of monadic second-order logic, then they can be computed in polynomial time if restricted to graphs of tree width at most
k. In other words, they are fixed-parameter tractable (FPT) with parameter the tree width of the input graph.
HOMOMORPHISM AND SIGMA POLYNOMIALS Gillman, Richard Alan
International Journal of Mathematics and Mathematical Sciences,
1995, Letnik:
1995, Številka:
4
Journal Article
Recenzirano
Odprti dostop
By establishing a connection between the sigma polynomial and the homomorphism polynomial, many of the proofs for computing the sigma polynmial are simplified, the homomorphism polynomial can be ...identified for several new classes of graphs, and progress can be made on identifying homomorphism polynomials.
New Results for the Martin Polynomial Ellis-Monaghan, Joanna A.
Journal of combinatorial theory. Series B,
November 1998, 1998-11-00, Letnik:
74, Številka:
2
Journal Article
Recenzirano
Odprti dostop
Algebraic techniques are used to find several new combinatorial interpretations for valuations of the Martin polynomial,M(G;s), for unoriented graphs. The Martin polynomial of a graph, introduced by ...Martin in his 1977 thesis, encodes information about the families of closed paths in Eulerian graphs. The new results here are found by showing that the Martin polynomial is a translation of a universal skein-type graph polynomialP(G) which is a Hopf map, and then using the recursion and induction which naturally arise from the Hopf algebra structure to extend known properties. Specifically, whenP(G) is evaluated by substitutingsfor all cycles and 0 for all tails, thenP(G) equalssM(G;s+2) for all Eulerian graphsG. The Hopf-algebraic properties ofP(G) are then used to extract new properties of the Martin polynomial, including an immediate proof for the formula forM(G;s) on disjoint unions of graphs, combinatorial interpretations forM(G;2+2k) andM(G;2−2k) withk∈Z⩾0, and a new formula for the number of Eulerian orientations of a graph in terms of the vertex degrees of its Eulerian subgraphs.
Partition functions and graph polynomials have found many applications in combinatorics, physics, biology and even the mathematics of finance. Studying their complexity poses some problems. To ...capture the complexity of their combinatorial nature, the Turing model of computation and Valiant's notion of counting complexity classes seem most natural. To capture the algebraic and numeric nature of partition functions as real or complex valued functions, the Blum-Shub-Smale (BSS) model of computation seems more natural. As a result many papers use a naive hybrid approach in discussing their complexity or restrict their considerations to sub-fields of C which can be coded in a way to allow dealing with Turing computability. In this paper we propose a unified natural framework for the study of computability and complexity of partition functions and graph polynomials and show how classical results can be cast in this framework.
PDF
