Source author record

Martin Trinks

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

10works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

A survey on recurrence relations for the independence polynomial of hypergraphs

The independence polynomial of a hypergraph is the generating function for its independent (vertex) sets with respect to their cardinality. This article aims to discuss several recurrence relations for the independence polynomial using some vertex and edge operations. Further, an extension of the well-known recurrence relation for simple graphs to hypergraphs is proven and other novel recurrence relations are also discussed.

preprint2014arXiv

Polynomial reconstruction of the matching polynomial

The matching polynomial of a graph is the generating function of the numbers of its matchings with respect to their cardinality. A graph polynomial is polynomial reconstructible, if its value for a graph can be determined from its values for the vertex-deleted subgraphs of the same graph. This note discusses the polynomial reconstructibility of the matching polynomial. We collect previous results, prove it for graphs with pendant edges and disprove it for some graphs.

preprint2014arXiv

The Merrifield-Simmons conjecture also holds for parity graphs

The Merrifield-Simmons conjectures states a relation between the distance of vertices in a simple graph $G$ and the number of independent sets, denoted as $σ(G)$ , in vertex-deleted subgraphs. Namely, that the sign of the term $σ(G_{-u}) \cdot σ(G_{-v}) - σ(G) \cdot σ(G_{-u-v})$ only depends on the parity of the distance of $u$ and $v$ in $G$ . We prove this statement in the case of parity graphs and give some evidence that this result may not be further generalized to other classes of graphs.

preprint2012arXiv

A note on a Broken-cycle Theorem for hypergraphs

Whitney's Broken-cycle Theorem states the chromatic polynomial of a graph as a sum over special edge subsets. We give a definition of cycles in hypergraphs that preserves the statement of the theorem there.

preprint2012arXiv

Proving properties of the edge elimination polynomial using equivalent graph polynomials

Averbouch, Godlin and Makowsky define the edge elimination polynomial of a graph by a recurrence relation with respect to the deletion, contraction and extraction of an edge. It generalizes some well-known graph polynomials such as the chromatic polynomial and the matching polynomial. By introducing two equivalent graph polynomials, one enumerating subgraphs and the other enumerating colorings, we show that the edge elimination polynomial of a simple graph is reconstructible from its polynomial deck and that it encodes the degree sequence of an arbitrary graph.

preprint2012arXiv

Recurrence relations and splitting formulas for the domination polynomial

The domination polynomial D(G,x) of a graph G is the generating function of its dominating sets. We prove that D(G,x) satisfies a wide range of reduction formulas. We show linear recurrence relations for D(G,x) for arbitrary graphs and for various special cases. We give splitting formulas for D(G,x) based on articulation vertices, and more generally, on splitting sets of vertices.

preprint2011arXiv

From spanning forests to edge subsets

We give some insight into Tutte's definition of internally and externally active edges for spanning forests. Namely we prove, that every edge subset can be constructed from the edges of exactly one spanning forest by deleting a unique subset of the internally active edges and adding a unique subset of the externally active edges.

preprint2011arXiv

The covered components polynomial: A new representation of the edge elimination polynomial

Motivated by the definition of the edge elimination polynomial of a graph we define the covered components polynomial counting spanning subgraphs with respect to their number of components, edges and covered components. We prove a recurrence relation, which shows that both graph polynomials are substitution instances of each other. We give some properties of the covered components polynomial and some results concerning relations to other graph polynomials.

preprint2010arXiv

Counting Connected Set Partitions of Graphs

Let $G=(V,E)$ be a simple undirected graph with $n$ vertices then a set partition $π=\{V_1, ..., V_k\}$ of the vertex set of $G$ is a connected set partition if each subgraph $G[V_j]$ induced by the blocks $V_j$ of $π$ is connected for $1\le j\le k$ . Define $q_{i}(G)$ as the number of connected set partitions in $G$ with $i$ blocks. The partition polynomial is then $Q(G, x)=\sum_{i=0}^n q_{i}(G)x^i$ . This paper presents a splitting approach to the partition polynomial on a separating vertex set $X$ in $G$ and summarizes some properties of the bond lattice. Furthermore the bivariate partition polynomial $Q(G,x,y)=\sum_{i=1}^n \sum_{j=1}^m q_{ij}(G)x^iy^j$ is briefly discussed, where $q_{ij}(G)$ counts the number of connected set partitions with $i$ blocks and $j$ intra block edges. Finally the complexity for the bivariate partition polynomial is proven to be $\sharp P$ -hard.

preprint2010arXiv

The Merrifield-Simmons conjecture holds for bipartite graphs

Let $G = (V, E)$ be a graph and $σ(G)$ the number of independent (vertex) sets in $G$ . Then the Merrifield-Simmons conjecture states that the sign of the term $σ(G_{-u}) \cdot σ(G_{-v}) - σ(G) \cdot σ(G_{-u-v})$ only depends on the parity of the distance of the vertices $u, v \in V$ in $G$ . We prove that the conjecture holds for bipartite graphs by considering a generalization of the term, where vertex subsets instead of vertices are deleted.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Martin Trinks

Research overview

Is this your work?

10 publications

A survey on recurrence relations for the independence polynomial of hypergraphs

Polynomial reconstruction of the matching polynomial

The Merrifield-Simmons conjecture also holds for parity graphs

A note on a Broken-cycle Theorem for hypergraphs

Proving properties of the edge elimination polynomial using equivalent graph polynomials

Recurrence relations and splitting formulas for the domination polynomial

From spanning forests to edge subsets

The covered components polynomial: A new representation of the edge elimination polynomial

Counting Connected Set Partitions of Graphs

The Merrifield-Simmons conjecture holds for bipartite graphs

See the researcher in context

Building this map preview