Barnetts gissning är en olöst fråga inom grafteorin om förekomsten av Hamiltons cykler i grafer. Hypotesen är uppkallad efter David W. Barnett, emeritus vid University of California, Davis . Gissningen säger att varje tvådelad polytopgraf med tre kanter vid varje vertex har en Hamiltonsk cykel.
En plan graf är en oriktad graf som kan bäddas in i ett euklidiskt utrymme utan skärningspunkter . En plan graf sägs vara polyedrisk (eller en polytopgraf) om och bara om den är vertex-3-ansluten , det vill säga om det inte finns två hörn vars borttagning delar upp grafen i två (eller flera) grafer. En graf kallas tvådelad om dess hörn kan färgas i två färger på ett sådant sätt att varje kant förbinder hörn av olika färger. En graf kallas kubisk (eller 3-regelbunden ) om varje vertex är slutet på exakt tre kanter. Slutligen en Hamiltonsk graf , om det finns en cykel som går igenom alla hörn exakt en gång. Barnetts gissning säger att varje kubisk tvådelad graf är en Hamiltonsk polytop.
Enligt Steinitz sats representerar en plan graf kanterna och hörnen på en konvex polyeder om och endast om den är polyedrisk. En 3-polytop bildar en kubisk graf om och bara om den är enkel . En plan graf är tvådelad om och endast om i dess plana inbäddning alla cykler av ytor (gränser) är av jämn längd. Således kan Barnetts gissning formuleras i en likvärdig form. Föreställ dig att en tredimensionell enkel konvex polyeder har ett jämnt antal kanter i varje yta. Sedan, enligt gissningen, har polyederns graf en Hamiltonsk cykel.
1884 antog Tate att varje kubisk polyedrisk graf är Hamiltonsk. Denna gissning är nu känd som Tate-förmodan . Gissningen vederlagdes av Tatt 1946 [1] genom att konstruera ett motexempel med 46 hörn. Andra forskare hittade senare mindre motexempel, men inget av dessa motexempel är tvådelade. Tutt själv antog att varje kubisk 3-kopplad tvådelad graf är Hamiltonsk, men ett motexempel hittades, Horton-grafen [2] [3] . David W. Barnett 1969 [4] föreslog en försvagad kombination av Tate- och Tutt-förmodan, och påstod att varje tvådelad kubisk polyedrisk graf är Hamiltonsk, eller motsvarande, att något motexempel på Tate-förmodan inte är tvådelat.
Kelmans [5] visade att Barnetts gissning är likvärdig med att säga att för två kanter e och f på samma yta av en tvådelad kubisk polytop, finns det en Hamiltonsk cykel som innehåller e men inte innehåller f . Det är tydligt att om påståendet är sant, så innehåller varje bipartit kubisk polyedral en Hamiltonsk cykel - välj bara e eller f . I en annan riktning visade Kelman att ett motexempel till detta uttalande kan omvandlas till ett motexempel på Barnetts ursprungliga gissning.
Barnetts gissning är också ekvivalent med påståendet att hörnen på den dubbla grafen för alla kubiska tvådelade polyedriska grafer kan delas in i två delmängder och de genererade graferna på dessa delmängder är träd. Sektionen som genereras av en sådan uppdelning i den dubbla grafen motsvarar den Hamiltonska banan i den ursprungliga grafen [6] .
Även om det inte är känt om Barnetts gissning är korrekt, visar beräkningsexperiment att det inte finns något motexempel med mindre än 86 hörn [7] [8] .
Om det visar sig att Barnetts gissning är felaktig, så kan det visas att kontroll av om en tvådelad kubisk polytop är Hamiltonian är ett NP-komplett problem [9] . Om en plan graf är tvådelad och kubisk, men bara 2-kopplad, så kanske den inte är Hamiltonsk, och att kontrollera om en graf är Hamiltonsk är ett NP-komplett problem [10] .
En gissning relaterad till Barnettes gissning säger att varje kubisk polyedrisk graf där alla ytor har sex eller färre kanter är Hamiltonian. Beräkningsexperiment har visat att om ett motexempel finns kommer det att ha mer än 177 hörn [11] .