Search

Abstract: Perfect vertex elimination schemes are part of the characterizations for several classes of graphs, including chordal and cop-win. Partial elimination schemes reduce a graph to an important subgraph, for example, -cores and robber-win graphs. We are interested in those partial elimination schemes, in which once a vertex is ready to be eliminated, it stays in that state regardless of which other vertices are eliminated. We show that in such a scheme, the sets of subsets of eliminated vertices, when ordered by inclusion, form an upper locally distributed lattice. We also show that (a) unless they contain a specific induced subgraph, the cop-win orderings have this property, and that (b) the process of cleaning graphs also leads to upper locally distributed lattices. Finally, we ask for an elimination scheme, which graphs are associated with distributive lattices? [Copyright &y& Elsevier]

Abstract: The independence polynomial of a graph G is the function , where is the number of independent sets of vertices in G of cardinality k. We investigate here the average independence polynomial, where the average is taken over all independence polynomials of (labeled) graphs of order n. We prove that while almost every independence polynomial has a nonreal root, the average independence polynomials always have all real, simple roots. [Copyright &y& Elsevier]