Publikation: Towards a computational proof of Vizing...
Stammdaten
Titel: | Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares |
Untertitel: | |
Kurzfassung: | Vizing's conjecture (open since 1968) relates the product of the domination numbers of two graphs to the domination number of their Cartesian product graph. In this paper, we formulate Vizing's conjecture as a Positivstellensatz existence question. In particular, we select classes of graphs according to their number of vertices and their domination number and encode the conjecture as an ideal/polynomial pair such that the polynomial is non-negative on the variety associated with the ideal if and only if the conjecture is true for this graph class. Using semidefinite programming we obtain numeric sum-of-squares certificates, which we then manage to transform into symbolic certificates confirming non-negativity of our polynomials. Specifically, we obtain exact low-degree sparse sum-of-squares certificates for particular classes of graphs. The obtained certificates allow generalizations for larger graph classes. Besides computational verification of these more general certificates, we also present theoretical proofs as well as conjectures and questions for further investigations. |
Schlagworte: | Vizing's conjecture, Algebraic model, Gröbner basis, Sum-of-squares problems, Semidefinite programming |
Publikationstyp: | Beitrag in Zeitschrift (Autorenschaft) |
Erscheinungsdatum: | 01.02.2021 (Online) |
Erschienen in: |
Journal of Symbolic Computation
Journal of Symbolic Computation
(
Elsevier;
)
zur Publikation |
Titel der Serie: | - |
Bandnummer: | 107 |
Heftnummer: | - |
Erstveröffentlichung: | Ja |
Version: | - |
Seite: | S. 67 - 105 |
Bild der Titelseite: |
Versionen
Keine Version vorhanden |
Erscheinungsdatum: | 01.02.2021 |
ISBN (e-book): | - |
eISSN: | - |
DOI: | http://dx.doi.org/10.1016/j.jsc.2021.01.003 |
Homepage: | https://www.sciencedirect.com/science/article/pii/S0747717121000092?via%3Dihub |
Open Access |
|
AutorInnen
Elisabeth Gaar
|
||||||
Daniel Krenn
|
||||||
Susan Margulies
|
||||||
Angelika Wiegele (intern) |
Zuordnung
Organisation | Adresse | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Kategorisierung
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Zitationsindex |
Informationen zum Zitationsindex: Master Journal List
|
Peer Reviewed |
|
Publikationsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
Arbeitsgruppen | Keine Arbeitsgruppe ausgewählt |
Kooperationen
Organisation | Adresse | ||
---|---|---|---|
Johannes Kepler Universität Linz
|
AT - 4040 Linz |
||
Paris-Lodron-Universität Salzburg
|
AT - 5020 Salzburg |
||
United States Naval Academy, Department of Mathematics
|
US Annapolis, MD |
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte: |
|
Publikationen: | Keine verknüpften Publikationen vorhanden |
Veranstaltungen: | Keine verknüpften Veranstaltung vorhanden |
Vorträge: | Keine verknüpften Vorträge vorhanden |