b'\n_START_ARTICLE_\nHipohamiltonov graf\n_START_PARAGRAPH_\nHipohamiltonov graf G je v teoriji grafov graf brez Hamiltonovega cikla, pri \xc4\x8demer postane vsak nov graf, ki nastane z odvzemanjem ene to\xc4\x8dke iz G, Hamiltonov. To mora veljati za vse to\xc4\x8dke grafa G.\n_START_SECTION_\nZgodovina\n_START_PARAGRAPH_\nHipohamiltonove grafe je najprej raziskoval Sousselier leta 1963 v delu Probl\xc3\xa8mes plaisants et d\xc3\xa9lectables. Lindgren je leta 1967 skonstruiral neskon\xc4\x8dno zaporedje hipohamiltonovih grafov. Navedel je \xc4\x8dlanka Gaudina, Herza in Rossija ter Busackra in Saatyja kot zgodnej\xc5\xa1a \xc4\x8dlanka o tej temi. \xc5\xa0e eno zgodnej\xc5\xa1e delo je \xc4\x8dlanek Herza, Dubyja in Vigu\xc3\xa9ja. Grafi v tem zaporedju imajo vsi \xc5\xa1tevilo to\xc4\x8dk enako  za vsako celo \xc5\xa1tevilo k. Enako zaporedje je neodvisno skonstruiral Sousselier._NEWLINE_Gr\xc3\xb6tschel je leta 1980 povzel veliko raziskovalnih dose\xc5\xbekov na tem podro\xc4\x8dju:\xc2\xa0\xc2\xbb\xc4\x8clanki, ki se ukvarjajo s temi grafi ... imajo po navadi nove razrede hipohamiltonovih ali hiposledljivih grafov, in ka\xc5\xbeejo, da za dolo\xc4\x8dene rede n tak\xc5\xa1ni grafi res obstajajo ali, da imajo nenavadne in nepri\xc4\x8dakovane zna\xc4\x8dilnosti.\xc2\xab\n_START_SECTION_\nRa\xc4\x8dunalni\xc5\xa1tvo\n_START_PARAGRAPH_\nHipohamiltonovi grafi se pojavljajo v celo\xc5\xa1tevilskem programiranju pri re\xc5\xa1itvah problema trgovskega potnika: dolo\xc4\x8dene vrste hipohamiltonovih grafov dolo\xc4\x8dajo facete politopa trgovskega potnika, oblike definirane kot konveksna ogrinja\xc4\x8da mno\xc5\xbeice mo\xc5\xbenih re\xc5\xa1itev problema trgovskega potnika. Te facete se lahko uporabijo v metodah prese\xc4\x8dne ravnine za re\xc5\xa1evanje problema. Gr\xc3\xb6tschel je leta 1980 opazil, da bo ra\xc4\x8dunska zahtevnost dolo\xc4\x8danja ali je graf hipohamiltonov, \xc4\x8deprav neznana, verjetno zelo velika, kar bo ote\xc5\xbeilo oskanje facet tak\xc5\xa1ne vrste razen za tiste, ki jih dolo\xc4\x8dajo majhni hipohamiltonovi grafi. K sre\xc4\x8di najmnaj\xc5\xa1i grafi vodijo do najmo\xc4\x8dnej\xc5\xa1ih neenakosti te uporabe._NEWLINE_Koncepte, tesno povezane s hipohamiltonostjo, so leta 2007 uporabili tudi Park, Lim in Kim pri merjenju okvarne odpornosti omre\xc5\xbene topologije za vzporedno ra\xc4\x8dunanje.\n_START_SECTION_\nZna\xc4\x8dilnosti\n_START_PARAGRAPH_\nVsak hipohamiltonov graf mora biti 3-to\xc4\x8dkovnopovezan, saj odstranjevanje poljubne to\xc4\x8dke vodi do Hamiltonovega cikla in poljubnih dveh to\xc4\x8dk do Hamiltonove poti, ki je povezana. Zaradi tega so posebej zanimivi kubi\xc4\x8dni hipohamiltonovi grafi saj imajo najmanj\xc5\xa1o mo\xc5\xbeno velikost (\xc5\xa1tevilo povezav) za dani red (\xc5\xa1tevilo to\xc4\x8dk). Obstaja n-to\xc4\x8dkovnohipohamiltonovih grafov v katerih je najve\xc4\x8dja stopnja enaka n/2 in v katerih je pribli\xc5\xbeno n\xc2\xb2/4 povezav._NEWLINE_Herz, Duby in Vigu\xc3\xa9 so leta 1967 domnevali, da ima vsak hipohamiltonov graf notranji obseg enak 5 ali ve\xc4\x8d. To je ovrgel Thomassen leta 1974, ko je na\xc5\xa1el protiprimera za notranji obseg 3 in 4._NEWLINE_Najmanj\xc5\xa1a hipohamiltonova grafa z notranjim obsegom 4 in 5 imata 10 to\xc4\x8dk, z notranjim obsegom 6 ima 25 to\xc4\x8dk, z notranjim obsegom 7 ima 28 to\xc4\x8dk.\n_START_SECTION_\nRavninskost\n_START_PARAGRAPH_\nNekaj \xc4\x8dasa ni bilo znano ali je hipohamiltonov graf lahko ravninski, sedaj pa je znanih ve\xc4\x8d primerov. Obstoj ravninskih hipohamiltonovih grafov so kot odprti problem postavili Chv\xc3\xa1tal, ter Chv\xc3\xa1tal, Klarner in Knuth leta 1972. Za konstrukcijo tak\xc5\xa1nega grafa so ponudili nagrado 5 $. Obstajala je tudi domneva, da tak\xc5\xa1nih grafov ni. Thomassen je leta 1976 uporabil Grinbergsov izrek za iskanje ravninskih hipohamiltonovih grafov z notranjim obsegom 3, 4 in 5, ter pokazal, da obstaja neskon\xc4\x8dno mnogo ravninskih hipohamiltonovih grafov, od katerih je najmanj\xc5\xa1i tak\xc5\xa1en graf na 105-ih to\xc4\x8dkah._NEWLINE_Najmanj\xc5\xa1i med njimi ima 40 to\xc4\x8dk. Na\xc5\xa1li so ga leta 2013 Jooyandeh, McKay, \xc3\x96sterg\xc3\xa5rd in Pettersson s pomo\xc4\x8djo ra\xc4\x8dunalni\xc5\xa1kega iskanja dolo\xc4\x8denih dru\xc5\xbein ravninskih grafov z notranjim obsegom 4 in Grinbergsovega izreka. Pred tem so na\xc5\xa1li majhne ravninske hipohamiltonove grafe s 57-imi, 48-imi in 42-imi to\xc4\x8dkami Hatzel (Hatzlov graf), Zamfirescu in Zamfirescu (48-Zamfirescujev graf), ter Wiener in Araja (Wiener-Arajev graf)._NEWLINE_Najmanj\xc5\xa1i ravninski hipohamiltonov graf z notranjim obsegom 5 ima 45 to\xc4\x8dk._NEWLINE_Najmanj\xc5\xa1i znani ravninski kubi\xc4\x8dni hipohamiltonov graf ima 70 to\xc4\x8dk._NEWLINE_Vsak ravninski hipohamiltonov graf ima vsaj eno to\xc4\x8dko z le tremi inciden\xc4\x8dnimi povezavami.\n_START_SECTION_\nRegularnost in barvanje\n_START_PARAGRAPH_\n\xc4\x8ce je kubi\xc4\x8dni graf Hamiltonov, se lahko njegove povezave pobarvajo s tremi barvami \xe2\x80\x93 dve alternirajo\xc4\x8di barvi za povezave v Hamiltonovem ciklu (ki mora po lemi o rokovanju imeti sodo dol\xc5\xbeino) in tretja barva za vse preostale povezave. Zaradi tega morajo biti vsi snarki, kubi\xc4\x8dni grafi brez mostov, za katere so za barvanje povezav potrebne \xc5\xa1tiri barve, nehamiltonovi. Mnogo znanih snarkov je taradi tega hipohamiltonovih. Vsak hipohamiltonov snark je bikriti\xc4\x8den \xe2\x80\x93 \xc4\x8de se odstrani poljubni dve to\xc4\x8dki, ostane podgraf, katerega povezave se lahko pobarvajo le s tremi barvami. Barvanje s tremi barvami tega podgrafa se preprosto opi\xc5\xa1e \xe2\x80\x93 po odstranitvi ene to\xc4\x8dke preostale to\xc4\x8dke vsebujejo Hamiltonov cikel. Po odstranitvi druge to\xc4\x8dke ta cikel postane pot, in njene povezave se lahko pobarvajo z izmenjavanjem dveh barv. Preostale povezave tvorijo parjenje in se lahko pobarvajo s tretjo barvo._NEWLINE_Barvni razredi poljubnega barvanja povezav s tremi barvami kubi\xc4\x8dnega grafa tvorijo tri tak\xc5\xa1na parjenja, da vsaka povezava pripada to\xc4\x8dno enemu parjenju. Hipohamiltonovi snarki nimajo particije v parjenje te vrste, in H\xc3\xa4ggkvist je leta 2007 domneval, da se lahko povezave kateregakoli hipohamiltonovega snarka uporabijo za oblikovanje \xc5\xa1estih tak\xc5\xa1nih parjenj, da vsaka povezava pripada to\xc4\x8dno enemu parjenju. To je posebni primer Berge-Fulkersonove domneve, da ima vsak snark \xc5\xa1est parjenj s to zna\xc4\x8dilnostjo.\n_START_SECTION_\nDvodelnost\n_START_PARAGRAPH_\nHipohamiltonovi grafi ne morejo biti dvodelni. V dvodelnem grafu se lahko to\xc4\x8dka izbri\xc5\xa1e in da Hamiltonov podgraf, \xc4\x8de pripada ve\xc4\x8djemu od dveh barvnih razredov grafa. Vendar se vsak dvodelni graf pojavi kot inducirani podgraf kak\xc5\xa1nega hipohamiltonovega grafa.\n_START_SECTION_\nZgledi\n_START_PARAGRAPH_\nNajmanj\xc5\xa1i hipohamiltonov graf je Petersenov graf. V splo\xc5\xa1nem je posplo\xc5\xa1eni Petersenov graf GP(n,2) hipohamiltonov za n enak 5 (mod 6). Petersenov graf je primer te konstrukcije za n\xc2\xa0=\xc2\xa05. Robertson je leta 1969 dokazal, da ti grafi niso Hamiltonovi, pri \xc4\x8demer se lahko neposredno preveri da odstranjevanja ene to\xc4\x8dke dajo Hamiltonov graf. Klasifikacijo nehamiltonovih posplo\xc5\xa1enih grafov je dal Alspach._NEWLINE_Lindgren je na\xc5\xa1el drug neskon\xc4\x8dni razred hipohamiltonovih grafov v katerih je \xc5\xa1tevilo to\xc4\x8dk enako 4 (mod 6). Lindgrenova konstrukcija se sestoji iz cikla dol\xc5\xbeine 3 (mod 6) in ene osrednje to\xc4\x8dke. Osrednja to\xc4\x8dka je povezana z vsako tretjo to\xc4\x8dko cikla s povezavami, ki jih je imenoval \xc5\xa1pice (spokes), to\xc4\x8dki dve dol\xc5\xbeini stran od vsake \xc5\xa1pice pa sta povezani med seboj. Spet je najmanj\xc5\xa1i primer njegove konstrukcije Petersenov graf._NEWLINE_Druge neskon\xc4\x8dne dru\xc5\xbeine so dali Bondy, Doyen in van Diest, ter Gutt.\n_START_SECTION_\nPosplo\xc5\xa1itve\n_START_PARAGRAPH_\nRaziskovali so tudi hiposledljive grafe, grafe, ki ne vsebujejo Hamiltonove poti, vendar tak\xc5\xa1ne, da se lahko vsaka podmno\xc5\xbeica n\xc2\xa0\xe2\x88\x92\xc2\xa01 to\xc4\x8dk pove\xc5\xbee s potjo. Ve\xc4\x8d avtorjev je obravnavalo analogne definicije hipohamiltonosti in hiposledljivosti za usmerjene grafe._NEWLINE_Enakovredna definicija hipohamiltonovih grafov je, da ima njihov najdalj\xc5\xa1i cikel dol\xc5\xbeino n\xc2\xa0\xe2\x88\x92\xc2\xa01 in da je presek vseh najdalj\xc5\xa1ih ciklov prazen. Menke, Zamfirescu in Zamfirescu so raziskali grafe z enako zna\xc4\x8dilnostjo, da je presek najdalj\xc5\xa1ih ciklov prazen, vendar v katerih je dol\xc5\xbeina najdalj\xc5\xa1ega cikla manj\xc5\xa1a od n\xc2\xa0\xe2\x88\x92\xc2\xa01. Herz je definiral cikli\xc4\x8dnost grafa kot najve\xc4\x8dje tak\xc5\xa1no \xc5\xa1tevilo k, da vsaka k to\xc4\x8dka pripada ciklu. Hipohamiltonovi grafi so ravno grafi s cikli\xc4\x8dnostjo n\xc2\xa0\xe2\x88\x92\xc2\xa01. Podobno so Park, Lim in Kim definirali graf, ki je \xc6\x92-okvarnoodporen hamiltonov, \xc4\x8de odstranitev najve\xc4\x8d \xc6\x92 to\xc4\x8dk da Hamiltonov podgraf. Schauerte in Zamfirescu sta raziskovala grafe s cikli\xc4\x8dnostjo n\xc2\xa0\xe2\x88\x92\xc2\xa02.'