فرض كنيد G=(V,E) گرافي باp راس و q يال باشد. يك پوشش گراف نماي غير دوري از G يك گردايه Y از مسيرها در G است كه به طور داخلي با هم مجزا هستند و هر يال گراف را دقيقا يك بار مي پوشانند. فرض كنيدf:V ® {1,2,…,p} يك برچسب گذاري دوسويي از رئوس گراف G باشد. فرض كنيد Gf گراف جهتداري باشد كه با جهتدهي به يال هاي uv از G از u به v به شرط اينكه f(u)<f(v) باشد، بدست آيد. اگر مجموعه Yf از تمام مسيرهاي جهتدار بيشين در Gf با ناديده گرفتن جهت ها يك پوشش گراف نماي غيردوري براي G باشد، در اينصورت f را يك برچسب گذاري گراف نماي G ناميده و G را يك گراف گراف نماي برچسبي مي ناميم.
و f} يك برچسب گذاري گراف نماي G استhl=min {|Yf |: عدد پوششي گراف نماي برچسبي G ناميده مي شود. در اين مقاله گراف هايي كه براي آنها (الف) hl=q-m، جاييكه m تعداد رئوس درجه 2 است و (ب) hl=q را مشخص مي كنيم. عدد پوششي گراف نماي برچسبي را براي گراف هاي تك دوري تعيين مي كنيم.