Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

graceful graph




A graph of points and connecting lines that can be numbered in a certain way. Say the graph has p points and e lines ("e" for edges) connecting them. Each of the points is assigned an integer; the lowest integer (by convention) is taken to be 0, and no two integers may be alike. Each of the lines is labeled with the difference between the two integers of the points that it connects. Then, if the numbers corresponding with the lines run from 0 through e, the graph is said to be graceful. Graceful graphs were originally defined and developed by Solomon Golomb.


Related category

   • GRAPHS AND GRAPH THEORY