Meinelin graafi on graafi, jossa missä tahansa parittomassa syklissä, jonka pituus on viisi tai enemmän, on vähintään kaksi sointua, eli kaksi reunaa, jotka yhdistävät syklin ei-naapuripisteitä [1] . Sointuja voi olla ei-leikkaus (kuten kuvassa), tai ne voivat leikata.
Meinelin graafit on nimetty Henry Meinelin mukaan (tunnetaan myös Meinelin olettamuksesta ), joka osoitti vuonna 1976 olevansa täydellisiä graafisia [2] kauan ennen kuin vahvisti vahvan täydellisen graafisen oletuksen , joka kuvaa täydellisesti täydelliset graafit. Markosyan ja Karapetyan löysivät itsenäisesti saman tuloksen [3] .
Meinelin graafit ovat täydellisten graafien alaluokka. Mikä tahansa Meinelin graafin luotu aligraafi on toinen Meinelin graafi, ja missä tahansa Meinelin graafissa suurimman klikkin koko on yhtä suuri kuin pienin määrä värejä, jotka tarvitaan graafin värittämiseen . Siten Meinelin graafit täyttävät täydellisen graafin määritelmän, jonka mukaan klikkiluku on yhtä suuri kuin minkä tahansa generoidun osagraafin kromaattinen luku [1] [2] [3] .
Meinel-graafia kutsutaan myös erittäin vahvasti täydellisiksi graafeiksi, koska (kuten Meinel ehdotti ja Hlang todisti) ne voidaan kuvata ominaisuudella, joka yleistää ehdottoman täydellisten graafien ominaisuuden määritelmän - missä tahansa Meinelin graafin generoidussa aligraafissa mikä tahansa kärki kuuluu riippumattomaan joukkoon , joka leikkaa minkä tahansa maksimaalisen klikkin [1] [4] .
Meinel-graafit sisältävät sointukaavioita , pariteettikaavioita ja niiden alaluokkia, intervallikaavioita , etäisyyden periytyviä graafisia , kaksiosaisia graafisia ja reunaperfekteitä graafisia [1] .
Vaikka Meinelin graafit muodostavat hyvin yleisen graafien alaluokan, ne eivät sisällä kaikkia täydellisiä kaavioita. Esimerkiksi talo (viisikulmio, jossa on yksi sointu) on täydellinen, mutta se ei ole Meinelin graafi.
Meinel-graafit voidaan tunnistaa polynomiajassa [5] , ja jotkin graafien optimointiongelmat, mukaan lukien graafin väritys , jotka ovat NP-kovia mielivaltaisille kaavioille, voidaan ratkaista polynomiajassa Meinelin graafisille [6] [7] .