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: Let be the set of well-covered graphs with no cycles of length 4. The main result is that if then can be partitioned, using an equivalence relation, into subsets such that: (i) each is well-covered; (ii) ; and (iii) the vector space of the well-covered weightings of G is the direct sum of the vector spaces of the well-covered weightings of the , each of which has dimension 1. Our second result is that the problem of determining whether an edge of a graph is incident with two vertices in the same equivalence class is NP-complete. We give a forbidden co-stable subgraph characterization of graphs in . Finally, we prove that graphs in of bounded maximum generalized degree can be recognized in polynomial time. [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]

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]

We investigate 1-, 2- and some k-digit (k⩾3) hexadecimal games with the help of a new arithmetic-periodicity theorem. We also note that not all hexadecimal games are periodic or arithmetic-periodic. [Copyright &y& Elsevier]

The k-polynomial of a simplicial complex C is the function kC(x)=∑i⩾1 fixi where fi is the number of i-faces in C. These k-polynomials are closed under composition, and we are lead to ask: for higher composites of a complex C with itself, what happens to the roots of their k-polynomials? We prove that they converge to the Julia set of kC(x), thereby associating with C a fractal. For 2-dimensional complexes we exploit the Mandelbrot set to determine when their fractals are connected, and determine the connectness of the fractals for certain families of ‘stripped’ complexes. [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]

Abstract: We consider edge critical graphs when playing cops and robber. Specifically, we look at those graphs whose copnumbers change from one to two when any edge is added, deleted, subdivided or contracted. We characterize all such sets, showing that they are empty, trees, all 2-edge-connected graphs and empty, respectively. We also consider those graphs which change from copnumber two to one when any edge is added, and give a characterization in the k-regular case. [Copyright &y& Elsevier]