I grafteorin är en matchningsgraf en graf som kan ritas på ett plan på ett sådant sätt att alla dess kanter är linjesegment med längden ett och kanterna inte skär varandra. Således har denna graf en inbäddning i planet både som en enhetsdistansgraf och som en plan graf . Informellt sett kan en matchningsgraf läggas ut av icke-korsande matchningar på en plan yta , därav namnet [1] .
Mycket forskning om tändsticksgrafer gäller vanliga grafer där varje vertex har samma antal grannar. Detta tal kallas graden av grafen.
Det är känt att det finns matchningsgrafer av alla grader upp till den fjärde. Kompletta grafer med en, två och tre hörn (en enda vertex, en kant och en triangel) är tändsticksgrafer, 0-, 1- respektive 2-regelbundna. Den minsta 3-regelbundna tändsticksgrafen bildas av två kopior av romber placerade så att motsvarande hörn är på enhetsavstånd. Dess dubbla tvådelade lock är grafen för ett åttakantigt prisma med skärningar [1] .
1986 presenterade Heiko Harbort Earl, som fick sitt namn - Earl of Harbort . Med 104 kanter och 52 hörn är denna graf det minsta kända exemplet på en 4- regelbunden matchningsgraf [2] . Grafen är stel [3] .
Det är omöjligt för en vanlig matchningsgraf att ha grader större än fyra [4] .
Som visas av Kurtz och Mazukolo [5] har den minsta 3-regelbundna triangelfria tändsticksgrafen (omkrets ≥ 4) 20 hörn. Dessutom presenterade de det minsta kända exemplet på en 3-regelbunden tändsticksgraf med omkrets 5 (180 hörn).
Att kontrollera om en given oriktad plan graf kan representeras som en tändsticksgraf är ett NP-hårt problem [6] [7]
Antalet olika (upp till isomorfism) matchningsgrafer är känt upp till tio kanter [8] [9] :
1, 1 , 3 , 5 , 12 , 28 , 74 , 207, 633, 2008, …