A Dynamic Survey of Graph Labeling

A Dynamic Survey of Graph Labeling

SUBMITTED: SEPTEMBER 1, 1996; ACCEPTED: NOVEMBER 14, 1997; THIS EDITION JANUARY 31, 2000 | JOSEPH A. GALLIAN
This article provides a comprehensive survey of graph labeling methods, focusing on graceful and harmonious labelings. Graceful labelings assign distinct labels to edges based on the difference of vertex labels, while harmonious labelings assign distinct labels to edges based on the sum of vertex labels modulo the number of edges. The article traces the origins of these methods to Rosa's 1967 work and Graham and Sloane's 1980 paper. It discusses the conditions under which graphs can be labeled gracefully or harmoniously, including parity conditions and degree constraints. The survey covers various graph classes, such as trees, cycle-related graphs, product graphs, complete graphs, disconnected graphs, and joins of graphs. It also explores variations of graceful labelings, such as α-labelings, and presents a summary of known results and open problems in the field. Despite the extensive research, few general results exist, and many conjectures remain unproven, particularly the Ringel-Kotzig conjecture about graceful trees.This article provides a comprehensive survey of graph labeling methods, focusing on graceful and harmonious labelings. Graceful labelings assign distinct labels to edges based on the difference of vertex labels, while harmonious labelings assign distinct labels to edges based on the sum of vertex labels modulo the number of edges. The article traces the origins of these methods to Rosa's 1967 work and Graham and Sloane's 1980 paper. It discusses the conditions under which graphs can be labeled gracefully or harmoniously, including parity conditions and degree constraints. The survey covers various graph classes, such as trees, cycle-related graphs, product graphs, complete graphs, disconnected graphs, and joins of graphs. It also explores variations of graceful labelings, such as α-labelings, and presents a summary of known results and open problems in the field. Despite the extensive research, few general results exist, and many conjectures remain unproven, particularly the Ringel-Kotzig conjecture about graceful trees.
Reach us at info@study.space
[slides] A Dynamic Survey of Graph Labeling | StudySpace