A gráfelmélet területén a hernyó (hernyógráf, hernyófa) olyan fa, melynek az összes csúcsa egy központi úttól legfeljebb egy él távolságra található.

A hernyókat először Harary és Schwenk tanulmányozták egy cikksorozatban. A név A. Hobbs leleménye.^[1][2] (Harary & Schwenk 1973) színes leírása szerint, „a hernyó olyan fa, ami metamorfózisa során úttá alakul át, ha a végpontgubóit eltávolítják.”^[1]

A következő karakterizációk mind jellemzik a hernyófákat:

• Olyan fák, melyek leveleit és az azokból kiinduló éleket eltávolítva útgráfot kapunk.^[2][3]
• Olyan fák, melyekben létezik minden 2 vagy magasabb fokszámú csúcsot tartalmazó út.
• Olyan fák, melyben minden legalább 3 fokszámú csúcsnak van legalább két olyan szomszédja, ami nem levél.
• Olyan fák, melyek nem tartalmazzák részgráfként a K_1,3 csillaggráf (karom) éleinek 2 hosszú útra cserélésével kapott gráfot.^[3]
• Olyan összefüggő gráfok, melyek lerajzolhatók úgy, hogy csúcsaik két párhuzamos egyenesen vannak, az élek pedig egymást nem metsző szakaszok, melyek végpontja valamelyik egyenesen van.^[3][4]
• Olyan fák, melyek négyzete Hamilton-féle. Tehát egy hernyóban létezik a csúcsok olyan körbeérő sorozata, melyben a sorozat szomszédos csúcsai 1 vagy 2 távolságra vannak egymástól; az olyan fákra, melyek nem hernyók, ez nem igaz. A sorozat előállítható például úgy, hogy a gráfot két párhuzamos egyenesre rajzoljuk föl, és az egyik egyenesen lévő csúcsok sorozatához hozzáfűzzük a másik egyenesen lévő csúcssorozat megfordítását.^[3]
• Olyan fák, melyek élgráfja Hamilton-utat tartalmaz; az út megkapható az említett két egyeneses felrajzolás éleinek rendezésével. Általánosabban, az élek száma, amit egy tetszőleges fa élgráfjához kell adni, hogy Hamilton-utat tartalmazzon (a Hamilton-kiegészítés mérete) megegyezik a fa közös élt nem tartalmazó hernyókra való „hernyófelbontásában” lévő hernyók minimális számával..^[5]
• Olyan összefüggő gráfok, melyekben az útszélesség 1.^[6]
• Összefüggő háromszögmentes intervallumgráfok.^[7]

Egy k-fa olyan merev körű gráf, melynek pontosan n − k maximális klikkje van, melyek mindegyike k + 1 csúcsot tartalmaz; az olyan k-fában, ami maga nem (k + 1)-klikk, minden maximális klikk vagy szétválasztja a gráfot két vagy több komponensre, vagy egyetlen levelet tartalmaz, mely levélcsúcs az egyetlen maximális klikkhez tartozik. Egy k-út olyan k-fa, aminek legalább két levele van, egy k-hernyó pedig olyan k-fa, ami felbontható egy k-útra és valahány k-levélre, melyek mindegyike szomszédos a k-út elvágó csúcshalmaz k-klikkjével. Ezt a terminológiát követve az 1-hernyó megegyezik a hernyógráffal, a k-hernyók pedig a k útszélességű élmaximális gráfok.^[6]

Egy homár vagy homárgráf (lobster) olyan fa, melynek minden csúcsa legfeljebb 2 él távolságra van egy központi úttól.^[8] Ez eggyel több, mint a hernyó esetében.

A hernyógráfok a gráfleszámlálási problémák azon ritka esetei közé tartoznak, melyekhez precíz képlet rendelhető: ha n ≥ 3, az n címkézetlen csúccsal rendelkező hernyók száma:^[1]

${\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.}$

Az n csúcsú hernyók száma n = 1, 2, 3, …-ra:

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, ... (A005418 sorozat az OEIS-ben).

Egy gráf feszítő hernyójának megtalálása (Spanning Caterpillar Problem) NP-teljes. Ezzel összefüggő optimalizációs probléma a minimális feszítő hernyó megtalálása (Minimum Spanning Caterpillar Problem, MSCP), ahol egy gráf élei duális költséggel rendelkeznek (levél- vagy út-költség) és a cél olyan hernyó megtalálása, ami kifeszíti a bemeneti gráfot és a lehető legalacsonyabb költséggel rendelkezik. Itt a hernyó költsége alatt az élek költségeinek összegét értjük, ahol minden élhez két külön költségérték tartozik, attól függően, hogy levél él vagy belső él. Nem létezik f(n)-approximációs algoritmus az MSCP megoldására, hacsak nem igaz, hogy P = NP. Itt f(n) alatt bármely polinom időben számítható függvényét értjük n-nek, a gráf csúcsszámának.^[9]

Létezik parametrizált algoritmus az MSCP optimális megoldására korlátozott favastagságú gráfokban. Mind a Spanning Caterpillar Problem, mind az MSCP megoldására léteznek lineáris idejű algoritmusok, ha a gráf külsíkgráf, soros-párhuzamos gráf vagy Halin-gráf.^[9]

A hernyógráfokat a kémiai gráfelméletben a benzolszerű szénhidrogén-molekulák szerkezetének ábrázolására használják. Ebben a reprezentációban a hernyó minden éle a molekuláris szerkezet egy 6 szénláncú gyűrűjének felel meg, két él akkor találkozik egy csúcsban, ha a megfelelő két gyűrű összekapcsolódik a struktúrákban. (El-Basil 1987) írja: „Csodálatos, hogy szinte minden gráfnak, ami fontos szerepet kapott abban, amit most »kémiai gráfelméletnek« nevezünk, köze lehet a hernyógráfokhoz”. Ebben a kontextusban a hernyógráfokat benzenoid fáknak és Gutman-fáknak is nevezik, Ivan Gutman munkássága nyomán.^[2][10][11]

• Weisstein, Eric W.: Caterpillar (angol nyelven). Wolfram MathWorld