BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
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 the domination polynomials of families of graphs obtained by various products, ranging from explicit formulae and recurrences for specific families to more general results. As an application, we show the domination polynomial is computationally hard to evaluate.
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.
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 paper representations of D(G,x) as a sum over subsets of the edge and vertex set of G. One of our main results is a representation of D(G,x) as a sum ranging over spanning bipartite subgraphs of G. We call a graph G conformal if all of its components are of even order. We show that the number of dominating sets of G equals a sum ranging over vertex-induced conformal subgraphs of G.
Let G=(V,E) be an undirected loopless graph with possible parallel edges and s and t be two vertices of G. Assume that vertex s is labelled at the initial time step and that every labelled vertex copies its labelling to neighbouring vertices along edges with one labelled endpoint independently with probability p in one time step. In this paper, we establish the equivalence between the expected s-t first arrival time of the above spread process and the notion of the stochastic shortest s-t path. Moreover, we give a short discussion of analytical results on special graphs including the complete graph and s-t series-parallel graphs. Finally, we propose some lower bounds for the expected s-t first arrival time.
Let G=(V,E) be a simple undirected graph with n vertices then a set partition π={V1,...,Vk} of the vertex set of G is a connected set partition if each subgraph G[Vj] induced by the blocks Vj of π is connected for 1≤j≤k. Define qi(G) as the number of connected set partitions in G with i blocks. The partition polynomial is then Q(G,x)=∑i=0nqi(G)xi. 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)=∑i=1n∑j=1mqij(G)xiyj is briefly discussed, where qij(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 ♯P-hard.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.