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
For each nonnegative integer i, let ai be the number of i-subsets of V(G) that induce an acyclic subgraph of a given graph G. We define A(G,x)=∑i≥0aixi (the generating function for ai) to be the acyclic polynomial for G. After presenting some properties of these polynomials, we investigate the nature and location of their roots.
The independence polynomial of a graph is the generating polynomial for the number of independent sets of each cardinality and its roots are called independence roots. We investigate here purely imaginary independence roots. We show that there are infinitely many connected graphs with purely imaginary independence roots and that every graph is a subgraph of such a graph. We also classify every rational purely imaginary number that is an independence root.
A dominating set S of a graph G of order n is a subset of the vertices of G such that every vertex is either in S or adjacent to a vertex of S. The domination polynomial is defined by D(G,x)=∑dkxk where dk is the number of dominating sets in G with cardinality k. In this paper we show that the closure of the real roots of domination polynomials is (−∞,0].
This papers focuses on the average order of dominating sets of a graph. We find the extremal graphs for the maximum and minimum value over all graphs on n vertices, while for trees we prove that the star minimizes the average order of dominating sets. We prove the average order of dominating sets in graphs without isolated vertices is at most 3n/4, but provide evidence that the actual upper bound is 2n/3. Finally, we show that the normalized average, while dense in [1/2,1], tends to 21 for almost all graphs.
A {\em restraint} on a (finite undirected) graph G=(V,E) is a function r on V such that r(v) is a finite subset of N; a proper vertex colouring c of G is {\em permitted} by r if c(v)∈r(v) for all vertices v of G (we think of r(v) as the set of colours {\em forbidden} at v). Given a large number of colors, for restraints r with exactly one colour forbidden at each vertex the smallest number of colorings is permitted when r is a constant function, but the problem of what restraints permit the largest number of colourings is more difficult. We determine such extremal restraints for complete graphs and trees.
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.