Graph Cleaning

Graph Cleaning

Cleaning the graph-

Here are the basics of graph cleaning…

-Initially every edge and vertex of the graph is dirty

-A fixed number of brushes (the things used to clean the graph) start on a set of vertices

-Each brush may move on any dirty edges and may not move on any edges that are already cleaned

-A brush may not move back to a vertex it has already been on

-Vertex v is cleaned once all its incident edges are cleaned

-A graph is cleaned when every vertex has been cleaned

-If every vertex has been cleaned, it follows that every edge has been cleaned

An example of a graph cleaning is shown below:

The two little sunlike shaped things are the brushes and each dotted line represents a cleaned edge, while a solid line represents a dirty edge. As you can see, two brushes are sufficient when cleaning this graph.

Now that we’ve got some of the basics, let’s dig into the math behind how many brushes you need to clean a graph.

Upper Bounds:

First, you’ll need to know that the brush path of a brush b is the path formed by the set of edges cleaned by b and is denoted b(G). Now that we know that, the upper bound of a general graph can be found using theorem 1.

Theorem 1:

for any graph G = (V, E).

The proof for this is long and this isn’t really what I wanted to get to anyways, so I’ll leave it out, but you can find it here if you’d like to read through it.

This theorem leads directly into a corollary which dives into a more specific category of graphs, d-regular graphs. For those of you who haven’t taken graph theory and those of you who may have forgotten, a regular graph is one in which all vertices have the same degree, which is the number of edges connected to that vertex. So a d-regular graph is one in which all vertices have degree d.

Here are a couple examples of d-regular graphs (although in this case r represents the degree and n is the number of vertices):

Corollary 1:

Let G = (V, E) be a d-regular graph on n vertices

If d is even, then   

If d is odd, then         

Now that we have an upper bound for d-regular graphs (yay) let’s look more closely at graphs with specific ds.

Cleaning on 2-regular graphs:

Let’s let Y_n be the number of cycles within a 2-regular graph with n vertices.

We can say every cycle needs exactly two brushes. Much like the cop vs robber version of this, each brush can move towards the other until all edges are cleaned which is where the robber would get caught.

Since we know that each cycle needs two brushes we can say that every 2-regular graph needs 2Y_n brushes.

Cleaning on 3-regular graphs:

In a 3-regular graph there exists a Hamiltonian cycle, which is another graph theory term. A Hamiltonian cycle is a path of edges that connect to each vertex exactly once. Here’s an example of one:

As you can see all the vertices are hit and it creates a cycle, but not all the edges need to be used or even can all be used in this case.

Due to 3-regular graphs having a Hamiltonian cycle, the number of brush paths on the graph is at least n/2 + 2. This is because one brush will be used for the Hamiltonian cycle, one will be used to complete the cycle, and the other n/2 are used to fill in the edges left out of the cycle.

Cleaning on 4-regular graphs:

A random 4-regular graph can be decomposed into two edge-disjoint Hamilton cycles, and hence four brush paths are made.

Conclusion:

Well now you know how to clean a graph and how many brushes are needed for general and d-regular graphs!

https://www.math.uwaterloo.ca/~nwormald/papers/clean_dregj.pdf

https://www.google.com/url?sa=i&rct=j&q=&esrc=s&source=images&cd=&cad=rja&uact=8&ved=0ahUKEwj6_6mdlMbSAhUK5iYKHaGoBNgQjhwIBQ&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FHamiltonian_path&psig=AFQjCNF_IcwSZPiaR4CfT3L_5p8G6h4GXQ&ust=1489036675190965