Hipohamiltonov graf G je v teoriji grafov graf brez Hamiltonovega cikla, pri čemer postane vsak nov graf, ki nastane z odvzemanjem ene točke iz G, Hamiltonov. To mora veljati za vse točke grafa G.^[2]

Hipohamiltonove grafe je najprej raziskoval Sousselier leta 1963 v delu Problèmes plaisants et délectables.^[3] Lindgren je leta 1967 skonstruiral neskončno zaporedje hipohamiltonovih grafov.^[1] Navedel je članka Gaudina, Herza in Rossija^[4] ter Busackra in Saatyja^[5] kot zgodnejša članka o tej temi. Še eno zgodnejše delo je članek Herza, Dubyja in Viguéja.^[6] Grafi v tem zaporedju imajo vsi število točk enako ${\displaystyle 6k+10\,}$ za vsako celo število k. Enako zaporedje je neodvisno skonstruiral Sousselier.^[6]

Grötschel je leta 1980^[7] povzel veliko raziskovalnih dosežkov na tem področju: »Članki, ki se ukvarjajo s temi grafi ... imajo po navadi nove razrede hipohamiltonovih ali hiposledljivih grafov, in kažejo, da za določene rede n takšni grafi res obstajajo ali, da imajo nenavadne in nepričakovane značilnosti.«

Hipohamiltonovi grafi se pojavljajo v celoštevilskem programiranju pri rešitvah problema trgovskega potnika: določene vrste hipohamiltonovih grafov določajo facete politopa trgovskega potnika, oblike definirane kot konveksna ogrinjača množice možnih rešitev problema trgovskega potnika. Te facete se lahko uporabijo v metodah presečne ravnine za reševanje problema.^[8][7][9] Grötschel je leta 1980^[7] opazil, da bo računska zahtevnost določanja ali je graf hipohamiltonov, čeprav neznana, verjetno zelo velika, kar bo otežilo oskanje facet takšne vrste razen za tiste, ki jih določajo majhni hipohamiltonovi grafi. K sreči najmnajši grafi vodijo do najmočnejših neenakosti te uporabe.^[10]

Koncepte, tesno povezane s hipohamiltonostjo, so leta 2007 uporabili tudi Park, Lim in Kim^[11] pri merjenju okvarne odpornosti omrežne topologije za vzporedno računanje.

Vsak hipohamiltonov graf mora biti 3-točkovnopovezan, saj odstranjevanje poljubne točke vodi do Hamiltonovega cikla in poljubnih dveh točk do Hamiltonove poti, ki je povezana. Zaradi tega so posebej zanimivi kubični hipohamiltonovi grafi saj imajo najmanjšo možno velikost (število povezav) za dani red (število točk).^[12] Obstaja n-točkovnohipohamiltonovih grafov v katerih je največja stopnja enaka n/2 in v katerih je približno n²/4 povezav.^[13]

Herz, Duby in Vigué so leta 1967^[6] domnevali, da ima vsak hipohamiltonov graf notranji obseg enak 5 ali več. To je ovrgel Thomassen leta 1974,^[14] ko je našel protiprimera za notranji obseg 3 in 4.

Najmanjša hipohamiltonova grafa z notranjim obsegom 4 in 5 imata 10 točk, z notranjim obsegom 6 ima 25 točk, z notranjim obsegom 7 ima 28 točk.^[15]

Nekaj časa ni bilo znano ali je hipohamiltonov graf lahko ravninski, sedaj pa je znanih več primerov. Obstoj ravninskih hipohamiltonovih grafov so kot odprti problem postavili Chvátal,^[16] ter Chvátal, Klarner in Knuth leta 1972.^[17] Za konstrukcijo takšnega grafa so ponudili nagrado 5 $. Obstajala je tudi domneva, da takšnih grafov ni.^[18] Thomassen^[19] je leta 1976 uporabil Grinbergsov izrek za iskanje ravninskih hipohamiltonovih grafov z notranjim obsegom 3, 4 in 5, ter pokazal, da obstaja neskončno mnogo ravninskih hipohamiltonovih grafov, od katerih je najmanjši takšen graf na 105-ih točkah.

Najmanjši med njimi ima 40 točk. Našli so ga leta 2013 Jooyandeh, McKay, Östergård in Pettersson^[20] s pomočjo računalniškega iskanja določenih družin ravninskih grafov z notranjim obsegom 4 in Grinbergsovega izreka. Pred tem so našli majhne ravninske hipohamiltonove grafe s 57-imi, 48-imi in 42-imi točkami Hatzel (Hatzlov graf)^[21], Zamfirescu in Zamfirescu (48-Zamfirescujev graf)^[22], ter Wiener in Araja (Wiener-Arajev graf).^[23]

• 
  Hatzlov graf na 57-ih točkah je ravninski hipohamiltonov graf z notranjim obsegom 4
• 
  48-Zamfirescujev graf na 48-ih točkah je ravninski hipohamiltonov graf z notranjim obsegom 4
• 
  Wiener-Arajev graf na 42-ih točkah je ravninski hipohamiltonov graf z notranjim obsegom 4

Najmanjši ravninski hipohamiltonov graf z notranjim obsegom 5 ima 45 točk.^[20]

Najmanjši znani ravninski kubični hipohamiltonov graf ima 70 točk.^[24]

Vsak ravninski hipohamiltonov graf ima vsaj eno točko z le tremi incidenčnimi povezavami.^[25]

Če je kubični graf Hamiltonov, se lahko njegove povezave pobarvajo s tremi barvami – dve alternirajoči barvi za povezave v Hamiltonovem ciklu (ki mora po lemi o rokovanju imeti sodo dolžino) in tretja barva za vse preostale povezave. Zaradi tega morajo biti vsi snarki, kubični grafi brez mostov, za katere so za barvanje povezav potrebne štiri barve, nehamiltonovi. Mnogo znanih snarkov je taradi tega hipohamiltonovih. Vsak hipohamiltonov snark je bikritičen – če se odstrani poljubni dve točki, ostane podgraf, katerega povezave se lahko pobarvajo le s tremi barvami.^[26][27] Barvanje s tremi barvami tega podgrafa se preprosto opiše – po odstranitvi ene točke preostale točke vsebujejo Hamiltonov cikel. Po odstranitvi druge točke 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.

Barvni razredi poljubnega barvanja povezav s tremi barvami kubičnega grafa tvorijo tri takšna parjenja, da vsaka povezava pripada točno enemu parjenju. Hipohamiltonovi snarki nimajo particije v parjenje te vrste, in Häggkvist je leta 2007^[28] domneval, da se lahko povezave kateregakoli hipohamiltonovega snarka uporabijo za oblikovanje šestih takšnih parjenj, da vsaka povezava pripada točno enemu parjenju. To je posebni primer Berge-Fulkersonove domneve, da ima vsak snark šest parjenj s to značilnostjo.

Hipohamiltonovi grafi ne morejo biti dvodelni. V dvodelnem grafu se lahko točka izbriše in da Hamiltonov podgraf, če pripada večjemu od dveh barvnih razredov grafa. Vendar se vsak dvodelni graf pojavi kot inducirani podgraf kakšnega hipohamiltonovega grafa.^[29]

Najmanjši hipohamiltonov graf je Petersenov graf.^[4][6] V splošnem je posplošeni Petersenov graf GP(n,2) hipohamiltonov za n enak 5 (mod 6). Petersenov graf je primer te konstrukcije za n = 5. Robertson je leta 1969^[30] dokazal, da ti grafi niso Hamiltonovi, pri čemer se lahko neposredno preveri da odstranjevanja ene točke dajo Hamiltonov graf. Klasifikacijo nehamiltonovih posplošenih grafov je dal Alspach.^[31]

Lindgren^[1] je našel drug neskončni razred hipohamiltonovih grafov v katerih je število točk enako 4 (mod 6). Lindgrenova konstrukcija se sestoji iz cikla dolžine 3 (mod 6) in ene osrednje točke. Osrednja točka je povezana z vsako tretjo točko cikla s povezavami, ki jih je imenoval špice (spokes), točki dve dolžini stran od vsake špice pa sta povezani med seboj. Spet je najmanjši primer njegove konstrukcije Petersenov graf.

Druge neskončne družine so dali Bondy,^[12] Doyen in van Diest,^[32] ter Gutt.^[33]

• 
  Petersenov graf na 10-ih točkah je najmanjši hipohamiltonov graf. Je neravninski kubični graf z notranjim obsegom 5
• 
  Sousselierjev graf na 16-ih točkah je hipohamiltonov graf z notranjim obsegom 5
• 
  Prvi Blanušev snark na 18-ih točkah je neravninski kubični hipohamiltonov graf z notranjim obsegom 5
• 
  Drugi Blanušev snark na 18-ih točkah je neravninski kubični hipohamiltonov graf z notranjim obsegom 5
• 
  Cvetlični snark J₅ na 20-ih točkah je neravninski kubični hipohamiltonov graf z notranjim obsegom 5
• 
  Prvi Loupekineov snark na 22-ih točkah je neravninski kubični hipohamiltonov graf z notranjim obsegom 5
• 
  Drugi Loupekineov snark na 22-ih točkah je neravninski kubični hipohamiltonov graf z notranjim obsegom 5
• 
  Coxetrov graf na 28-ih točkah je neravninski kubični hipohamiltonov graf z notranjim obsegom 7
• 
  Snark dvojna zvezda na 30-ih točkah je neravninski kubični hipohamiltonov graf z notranjim obsegom 6
• 
  Szekeresov snark na 50-ih točkah je neravninski kubični hipohamiltonov graf z notranjim obsegom 5

Chvátal je leta 1973 dokazal, da za vsak dovolj velik n obstaja hipohamiltonov graf z n točkami. Kasnejša odkritja^[34][32] so dala točnejši pomen za »dovolj velik« in je sedaj znano, da takšni grafi obstajajo za vse n ≥ 18. Znan je celotni seznam neizomorfnih hipohamiltonovih grafov z največ 17-imi točkami^[35] (OEIS A141150):

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 4, 0, (13), ...

To so Petersenov graf na 10-ih točkah, graf na 13-ih točkah in graf na 15-ih točkah, ki ga je z računalniškim iskanjem našel Herz,^[36], ter štirje grafi na 16-ih točkah. Na 18-ih točkah obstaja vsaj trinajst neizomorfnih hipohamiltonovih grafov in od teh sta dva kubična grafa.^[35] Število kubičnih hipohamiltonovih grafov reda n > 0 je:

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 3, 0, 1, 0, 100, 0, 34, 0, 1, 0, ...

S pomočjo Chvátalove metode flip-flop^[16] na Petersenovem grafu in cvetličnem snarku je mogoče pokazati, da število neizomorfnih hipohamiltonovih grafov in še posebej število neizomorfnih hipohamiltonovih snarkov narašča eksponentno s številom točk.^[29][37][38]

Raziskovali so tudi hiposledljive grafe, grafe, ki ne vsebujejo Hamiltonove poti, vendar takšne, da se lahko vsaka podmnožica n − 1 točk poveže s potjo.^{[39][40][18][34]} Več avtorjev je obravnavalo analogne definicije hipohamiltonosti in hiposledljivosti za usmerjene grafe.^{[41][42][43][25]}

Enakovredna definicija hipohamiltonovih grafov je, da ima njihov najdaljši cikel dolžino n − 1 in da je presek vseh najdaljših ciklov prazen. Menke, Zamfirescu in Zamfirescu^[44] so raziskali grafe z enako značilnostjo, da je presek najdaljših ciklov prazen, vendar v katerih je dolžina najdaljšega cikla manjša od n − 1. Herz^[36] je definiral cikličnost grafa kot največje takšno število k, da vsaka k točka pripada ciklu. Hipohamiltonovi grafi so ravno grafi s cikličnostjo n − 1. Podobno so Park, Lim in Kim^[11] definirali graf, ki je ƒ-okvarnoodporen hamiltonov, če odstranitev največ ƒ točk da Hamiltonov podgraf. Schauerte in Zamfirescu^[45] sta raziskovala grafe s cikličnostjo n − 2.

• podhamiltonov graf

• Weisstein, Eric Wolfgang. »Hypohamiltonian Graph«. MathWorld.