Lecture: Tackling Vizing’s conjecture on graphs with SDP
Master data
Title: | Tackling Vizing’s conjecture on graphs with SDP |
Description: | In 1968 Vizing conjectured, that the product of domination number of two graphs is always smaller or equal to the domination number of the product graph. Today, we still don't know whether this conjecture is true or not. In this talk we will investigate a completely new way of tackling Vizing's conjecture. First we will build an algebraic model of the conjecture with some parameters. Then we will translate Vizing's conjecture for these parameters into the question of whether a specific polynomial is nonnegative over a specific ideal. Then we will do another reformulation to the question of whether a specific polynomial is a sum-of-squares polynomial and discuss how we can use semidefinite programming to answer these kind of questions. Eventually we will discuss our obtained results, which provide a proof of concept of our new method to tackle Vizing's conjecture. |
Keywords: |
Type: | Guest lecture |
Homepage: | - |
Event: | mathematical seminar (University of Tilburg) |
Date: | 14.03.2019 |
lecture status: |
Assignment
Organisation | Address | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Categorisation
Subject areas | |
Research Cluster | No research Research Cluster selected |
Focus of lecture |
Classification raster of the assigned organisational units:
|
Group of participants |
|
Published? |
|
working groups | No working group selected |
Cooperations
No partner organisations selected
Research activities
All related research activities to this event are shown here. With the link below, you can view them in the search view where you are also able to export them.
Show related search activities in search
Projects |
|
Publications | No related publications |
Events | No related events |
Lectures | No related lectures |