ใน สาขาวิชา คณิตศาสตร์ของทฤษฎีกราฟการติดป้ายกราฟคือการกำหนดป้ายกำกับ ซึ่งโดยทั่วไปแทนด้วย^{จำนวนเต็ม}ให้กับขอบและ/หรือจุดยอดของกราฟ [ ^{1 ]}

ตามหลักการแล้ว เมื่อกำหนดกราฟG = ( V , E )การกำหนดป้ายกำกับจุดยอดคือฟังก์ชันของVไปยังเซตของป้ายกำกับ กราฟที่มีฟังก์ชันดังกล่าวเรียกว่ากราฟที่มีป้ายกำกับจุดยอดในทำนองเดียวกันการกำหนดป้ายกำกับขอบคือฟังก์ชันของEไปยังเซตของป้ายกำกับ ในกรณีนี้ กราฟเรียกว่ากราฟ ที่มีป้ายกำกับขอบ

เมื่อป้ายกำกับขอบเป็นสมาชิกของเซตที่มีลำดับ (เช่นจำนวนจริง ) เราอาจเรียกกราฟนั้นว่า กราฟ ถ่วง น้ำหนัก

เมื่อใช้โดยไม่มีคุณสมบัติเพิ่มเติม คำว่ากราฟที่มีป้ายกำกับโดยทั่วไปหมายถึงกราฟที่มีป้ายกำกับที่จุดยอด โดยที่ป้ายกำกับทั้งหมดแตกต่างกัน กราฟดังกล่าวอาจมีป้ายกำกับเทียบเท่ากับจำนวนเต็มที่ต่อเนื่องกัน{ 1, …, | V | }โดยที่| V |คือจำนวนจุดยอดในกราฟ^{[ 1 ]}สำหรับการใช้งานหลายอย่าง ขอบหรือจุดยอดจะได้รับป้ายกำกับที่มีความหมายในโดเมนที่เกี่ยวข้อง ตัวอย่างเช่น ขอบอาจได้รับน้ำหนักที่แสดงถึง "ต้นทุน" ในการเดินทางระหว่างจุดยอดที่เชื่อมต่อกัน^{[ 2 ]}

ในคำจำกัดความข้างต้น กราฟจะเข้าใจว่าเป็นกราฟแบบง่ายที่ไม่มีทิศทางและจำกัด อย่างไรก็ตาม แนวคิดของการติดป้ายกำกับอาจนำไปใช้กับส่วนขยายและการวางนัยทั่วไปของกราฟทั้งหมดได้ ตัวอย่างเช่น ในทฤษฎีออโตมาตาและ ทฤษฎี ภาษาทางการ การพิจารณา มัลติกราฟที่มีป้ายกำกับนั้นสะดวกกว่า กล่าวคือ คู่จุดยอดอาจเชื่อมต่อกันด้วยขอบที่มีป้ายกำกับหลายเส้น^{[ 3 ]}

การติดป้ายกราฟส่วนใหญ่สืบย้อนต้นกำเนิดมาจากการติดป้ายที่นำเสนอโดย Alexander Rosa ในบทความปี 1967 ของเขา^{[ 4 ]} Rosa ระบุการติดป้ายสามประเภท ซึ่งเขาเรียกว่าการติดป้ายα , βและρ ^{[ 5 ]} ต่อมา Solomon Golombได้เปลี่ยนชื่อการติดป้ายβ เป็น "graceful" และชื่อนี้ก็ได้รับความนิยมตั้งแต่นั้นเป็นต้นมา

กราฟจะเรียกว่ากราฟสง่างาม (graceful graph) ก็ต่อเมื่อจุดยอดของกราฟมีป้ายกำกับตั้งแต่0ถึง| E |ซึ่งเป็นขนาดของกราฟ และการกำหนดป้ายกำกับจุดยอดนี้ทำให้เกิดการกำหนดป้ายกำกับขอบตั้งแต่1ถึง| E |สำหรับขอบใดๆeป้ายกำกับของeคือผลต่างบวกระหว่างป้ายกำกับของจุดยอดสองจุดที่เชื่อมต่อกับeกล่าวคือ ถ้าeเชื่อมต่อกับจุดยอดที่มีป้ายกำกับiและjแล้วeจะมีป้ายกำกับเป็น| i − j |ดังนั้น กราฟG = ( V , E )จะเป็นกราฟสง่างามก็ต่อเมื่อมีฟังก์ชันหนึ่งต่อหนึ่ง (injection) จากVไปยัง{0, ..., | E |}ที่ทำให้เกิดฟังก์ชันหนึ่งต่อหนึ่งทั่วถึง (bijection) จากEไปยัง{1, ..., | E | }

ในบทความต้นฉบับของเขา Rosa พิสูจน์ว่ากราฟออยเลอร์ ทั้งหมด ที่มีขนาดเทียบเท่ากับ1หรือ2 ( mod 4 ) ไม่ใช่กราฟสง่างาม การที่กราฟบางตระกูลเป็นกราฟสง่างามหรือไม่นั้นเป็นหัวข้อหนึ่งในทฤษฎีกราฟที่มีการศึกษาอย่างกว้างขวาง อาจกล่าวได้ว่าข้อสันนิษฐานที่ยังไม่ได้รับการพิสูจน์ที่ใหญ่ที่สุดในการติดป้ายกราฟคือข้อสันนิษฐานของ Ringel–Kotzig ซึ่งตั้งสมมติฐานว่าต้นไม้ทั้งหมดเป็นกราฟสง่างาม สิ่งนี้ได้รับการพิสูจน์แล้วสำหรับเส้นทาง ทั้งหมด หนอนผีเสื้อและตระกูลต้นไม้อนันต์อื่นๆ อีกมากมายAnton Kotzigเองเรียกความพยายามในการพิสูจน์ข้อสันนิษฐานนี้ว่าเป็น "โรค" ^{[ 6 ]}

การกำหนดป้ายกำกับขอบอย่างสง่างาม (edge-graceful labeling) บนกราฟแบบง่ายที่ไม่มีวงวนหรือขอบหลายเส้น บน จุดยอด pจุดและ ขอบ qเส้น คือการกำหนดป้ายกำกับขอบด้วยจำนวนเต็มที่แตกต่างกันใน{1, …, q }โดยที่ป้ายกำกับบนจุดยอดที่กำหนดโดยการกำหนดป้ายกำกับจุดยอดด้วยผลรวมของขอบที่เชื่อมต่อซึ่งคำนวณแบบโมดูลัสpจะกำหนดค่าทั้งหมดตั้งแต่ 0 ถึงp − 1ให้กับจุดยอดนั้น กราฟGเรียกว่า "กราฟขอบอย่างสง่างาม" (edge-graceful) ถ้ากราฟนั้นยอมรับการกำหนดป้ายกำกับขอบอย่างสง่างามได้

การติดฉลากขอบที่สง่างามได้รับการแนะนำครั้งแรกโดย Sheng-Ping Lo ในปี 1985 ^{[ 7 ]}

เงื่อนไขที่จำเป็นสำหรับกราฟที่จะมีขอบที่สวยงามคือ "เงื่อนไขของโล":

${\displaystyle q(q+1)={\frac {p(p-1)}{2}}\mod p.}$

“การติดป้ายกำกับที่สอดคล้องกัน” บนกราฟGคือการส่งแบบหนึ่งต่อหนึ่งจากจุดยอดของGไปยังกลุ่มของจำนวนเต็มมอดูลkโดยที่kคือจำนวนขอบของGซึ่งทำให้เกิด การส่งแบบหนึ่งต่อหนึ่ง ทั่วถึงระหว่างขอบของGและจำนวนมอดูลkโดยการใช้ป้ายกำกับขอบสำหรับขอบ( x , y )เป็นผลรวมของป้ายกำกับของจุดยอดสองจุดx , y (mod k ) “กราฟที่สอดคล้องกัน” คือกราฟที่มีการติดป้ายกำกับที่สอดคล้องกันวงจรคี่เป็นกราฟที่สอดคล้องกัน เช่นเดียวกับกราฟ Petersenมีการคาดการณ์ว่าต้นไม้ทั้งหมดเป็นกราฟที่สอดคล้องกันหากอนุญาตให้ใช้ป้ายกำกับจุดยอดซ้ำได้_[ ^{8 ]กราฟหนังสือ}เจ็ด หน้าK1,7 × K2เป็นตัวอย่างของกราฟที่ไม่สอดคล้องกัน^{[ 9} _]

การระบายสีกราฟเป็นคลาสย่อยของการติดป้ายกราฟ การระบายสีจุดยอดจะกำหนดป้ายที่แตกต่างกันให้กับจุดยอดที่อยู่ติดกัน ในขณะที่การระบายสีขอบจะกำหนดป้ายที่แตกต่างกันให้กับขอบที่อยู่ติดกัน^{[ 10 ]}

การติดป้ายนำโชคของกราฟGคือการกำหนดจำนวนเต็มบวกให้กับจุดยอดของGโดยที่ถ้าS ( v )แทนผลรวมของป้ายบนจุดยอดข้างเคียงของvแล้วSคือการระบายสีจุดยอดของG "เลขนำโชค" ของG คือ kที่น้อยที่สุดที่ทำให้Gมีการติดป้ายนำโชคด้วยจำนวนเต็ม{1, …, k } ^{[ 11 ]}

การติดฉลากแอนติเมจิกของกราฟGคือการกำหนดจำนวนเต็มบวก{1,..., | E | } แบบหนึ่งต่อหนึ่งให้กับขอบของGโดยที่น้ำหนักของจุดยอดที่เหนี่ยวนำทั้งหมดจะแตกต่างกัน โดยที่น้ำหนักของจุดยอดคือผลรวมของฉลากบนขอบทั้งหมดที่เชื่อมต่อกับจุดยอดนั้น^{[ 12 ]}

การกำหนดป้ายกำกับ วิเศษ(ระยะทาง)ให้กับกราฟGคือการกำหนดค่าแบบหนึ่งต่อหนึ่งของจำนวนเต็มบวก{1,..., | V | } ให้กับจุดยอดของGโดยที่น้ำหนักของจุดยอดทั้งหมดเท่ากับจำนวนเต็มบวกk บางค่า น้ำหนักของ จุดยอดคือผลรวมของป้ายกำกับของจุดยอดทั้งหมดที่อยู่ติดกับจุดยอดนั้น ค่าคงที่ kดังกล่าวหากมีอยู่ จะเรียกว่าค่าคงที่วิเศษของกราฟ