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: Following the decontamination metaphor for searching a graph, we introduce a cleaning process, which is related to both the chip-firing game and edge searching. Brushes (instead of chips) are placed on some vertices and, initially, all the edges are dirty. When a vertex is ‘fired’, each dirty incident edge is traversed by only one brush, cleaning it, but a brush is not allowed to traverse an already cleaned edge; consequently, a vertex may not need degree-many brushes to fire. The model presented is one where the edges are continually recontaminated, say by algae, so that cleaning is regarded as an on-going process. Ideally, the final configuration of the brushes, after all the edges have been cleaned, should be a viable starting configuration to clean the graph again. We show that this is possible with the least number of brushes if the vertices are fired sequentially but not if fired in parallel. We also present bounds for the least number of brushes required to clean graphs in general and some specific families of graphs. [Copyright &y& Elsevier]

Abstract: Given a graph G and field , the well-covered vector space of G is the vector space of all functions such that is constant for all maximal independent sets I. We show here that, over all fields , almost all graphs has well-covered dimension 0 over . As a corollary, we prove that almost no graphs are well-covered. [Copyright &y& Elsevier]

Independence polynomials of graphs enjoy the property of essentially being closed under graph composition (or ‘lexicographic product’). We ask here: for higher products of a graph G with itself, where are the roots of their independence polynomials approaching? We prove that in fact they converge (in the Hausdorff topology) to the Julia set of the independence polynomial of G, thereby associating with G a fractal. The question arises as to when these fractals are connected, and for graphs with independence number 2 we exploit the Mandelbro¨t set to answer the question completely. [Copyright &y& Elsevier]