BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Martin Trinks

Martin Trinks contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CO

Trust snapshot

Quick read

Trust 21 - Emerging
10works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

10 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access