Student: Adam Juraszek CoRE Building; room 444 Charles University in Prague juriad@gmail.com DIMACS/DIMATIA REU See my personal gallery

## Projects

### I work on the following 2 projects.

#### Dominating Sets on Colored Tournaments

It is known that for one and two colors there is always a single dominator on a transitively colored tournament. We want to estimate an upper bound of the size of the dominating set depending only on the number of colors and not on the size of the graph.

#### Subclasses of Chordal Graphs

There are problems which can be solved in polynomial time on interval graphs but they are hard on general chordal graphs. We want to describe subclasses of chordal graphs (by fixing the tree) for which the problems are still easy/hard. In particular, we are interested in the description of groups of automorphisms of such graphs.

## Work Log

### What my team and I did during our 6 weeks at Rutgers University.

#### Arrival and choice of problems

We chose 4 problems that we want to work on and divided ourselves into groups of 3 or 4 people for each problem. We prepared presentation for Dr. Abello and our REU colleagues about what problems we chose and how we want to solve them.

#### Tournaments visualization and culture

We created a library in Python for working with colored tournaments including their visualization and simple hypothesis testing. We also generated tens of tournaments by CSP techniques in MiniZinc and tried to find out what they have in common. The later half of the week was spent preparing our presentation and game for Cultural Day.

#### More random tournaments

We developed a toolkit for deriving new tournaments from existing ones by substitution and removal of vertex. We found many graphs with three dominators but unfortunately all of them have either K9-K3K3 or K7-Paley as a subgraph. We also proved that other Paley tournaments (on 11 and more vertices) cannot be transitively colored by three colors.

There is a hypothesis that there doesn't exist a three-colored tournament with a linear dominator not having a cyclic dominator at the same time. So far, we could not find a graph with three dominators which doesn't contain the two mentioned subgraphs.

#### Graphs with three dominators

We proved that it is sufficient to look at graphs having a Hamiltonian circle, which allowed us to add powerful constraints to our model. We also found many tournaments on 10 vertices which don't contain K9-K3K3 or K7-Paley as subgraph. No significant progress in (dis)proving the hypothesis was achieved.

I spent some time on my other problems (recognition and expansion of T-Graphs) and helped Linda to grasp the concept of polynomial reduction in proofs of NP completeness. Nontrivial time was spent planning and organizing weekend trip to Harriman State Park and Bear Mountain State Park in NY.

#### Reducibility of tournaments

We proved that it is sufficient to look at strongly connected tournaments (having Hamiltonian circle) as all other strongly connected components are dominated by any vertex in the dominating component. We also introduced concept of tournament reduction as removal of vertices such that the size of minimum dominating set is the same. We observed a few properties of such minimum tournaments and found some on 10 and 11 vertices. We studied inductive construction of tournaments by introduction of new vertices while keeping track of the size of the minimum dominating set. We found some properties which a tournament must fulfill in order to achieve a minimum dominating set of size four.

#### Related classes of tournaments

We continued studying inductive construction and tried to find additional properties required by minimum counter-example of f(3) = 3. We also read a few articles regarding sizes of minimum dominating sets and reachability on related classes of tournaments. We found a connection between 3-colored tournaments and 2-majority graphs which seems promising.

I also attended an introductory lecture about programming. There was a robot with which we played a number guessing game, which we later developed in Scratch. I learned how to use variables, conditionals and loops. Although I don't know all the possibilites which it provides, I am pretty sure that it will prove to be useful in my future.

#### Final week

We found out that the result regarding 2-majority graphs is already known and also that it deals only with a specific subclass of tournaments. We started to write our final presentation and had a draft ready for our mentor on Wednesday. The presentation will be given to other REU participants on Friday.

We are going back to Prague on Saturday.

## Resources

### You can download presentations and other resources which we created during our research.

Date Description File
6/5/2015 Presentation of problems we chose to solve PRGpresentation1.pdf
6/12/2015 Questionnaire for Cultural Day questionnaire.pdf
6/12/2015 Labyrinth map, rules, and description of locations labyrinth.pdf
6/12/2015 Labyrinth questions questions.pdf
6/14/2015 Questionnaire results questionnaire-results.pdf
7/16/2015 Final presentation of our results PRGpresentation2.pdf
7/16/2015 Whole project (scripts and graphs) tournaments.zip

## Our Team

### We all are classmates from Charles University in Prague.

#### Tomáš Masařík

The leader; works on other problems.

#### Jitka Novotná

Works on tournaments and other problems.

#### Martin Töpfer

Works on tournaments, subclasses and other problems.

#### Tomáš Toufar

Works on subclasses and other problems.

#### Jan Voborník

Works on other problems.

#### Peter Zeman

Works on subclasses and other problems

## Our DIMACS Mentor

#### James Abello

Research Professor at DIMACS, Rutgers University