12 citations · 34 across the 17 of their papers we have counts for
9 papers · 1 filter
On the Tutte and matching polynomials for complete graphs
Tomer Kotek, Johann A. Makowsky
Let be the Tutte polynomial for graphs. We study the sequence where are non-negative integers, and show that for every the sequ…
On sequences of polynomials arising from graph invariants
T. Kotek, J. A. Makowsky, E. V. Ravve
Graph polynomials are deemed useful if they give rise to algebraic characterizations of various graph properties, and their evaluations encode many other graph invariants. Algebrai…
On the complexity of generalized chromatic polynomials
A. Goodall, M. Hermann, T. Kotek +2
J. Makowsky and B. Zilber (2004) showed that many variations of graph colorings, called CP-colorings in the sequel, give rise to graph polynomials. This is true in particular for h…
Recurrence Relations for Graph Polynomials on Bi-iterative Families of Graphs
Tomer Kotek, Johann A. Makowsky
We show that any graph polynomial from a wide class of graph polynomials yields a recurrence relation on an infinite class of families of graphs. The recurrence relations we obtain…
Domination Polynomials of Graph Products
Tomer Kotek, James Preen, Peter Tittmann
The domination polynomials of binary graph operations, aside from union, join and corona, have not been widely studied. We compute and prove recurrence formulae and properties of t…
Subset-Sum Representations of Domination Polynomials
Tomer Kotek, James Preen, Peter Tittmann
The domination polynomial D(G,x) is the ordinary generating function for the dominating sets of an undirected graph G=(V,E) with respect to their cardinality. We consider in this p…
Recurrence relations and splitting formulas for the domination polynomial
Tomer Kotek, James Preen, Frank Simon +2
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 r…
Definability of Combinatorial Functions and Their Linear Recurrence Relations
T. Kotek, J. A. Makowsky
We consider functions of natural numbers which allow a combinatorial interpretation as density functions (speed) of classes of relational structures, s uch as Fibonacci numbers, Be…
On the Reconstruction of Graph Invariants
T. Kotek
The reconstruction conjecture has remained open for simple undirected graphs since it was suggested in 1941 by Kelly and Ulam. In an attempt to prove the conjecture, many graph inv…