Connected Matchings in Graphs with Independence Number 2

Overview

In our everyday lives, networks play an important role: networks like the internet, the road system of a society, the atoms of a molecule or the neurons of a brain. The mathematical discipline for understanding networks is graph theory. In order to improve our knowledge on graph theory, Hadwiger's conjecture is crucial and yet, it is still not solved. Although I have not proved the Hadwiger's conjecture, I came up with the idea that will benefit our knowledge in graph theory, more specifically, on connected matchings. In this research, I study the size of the largest connected matching in graphs with largest independent set of size 2. I conjecture that if the graph has at least 4n-1 vertices then it contains a connected matching of size n. I prove my conjecture holds for n less than or equal to 13.

Competition history

• ISEF 2015 Category not listed · Entry MATH037I

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.