A Necessary Condition
Lo gave a necessary condition for a graph to be edge-graceful. It is that a graph with q edges and p vertices is edge graceful only if
- is congruent to modulo p.
or, in symbols,
This is referred to as Lo's condition in the literature. This follows from the fact that the sum of the labels of the vertices is twice the sum of the edges, modulo p. This is useful for disproving a graph is edge-graceful. For instance, one can apply this directly to the path and cycle examples given above.
Read more about this topic: Edge-graceful Labeling
Famous quotes containing the word condition:
“The pendulum oscillates between these two terms: Suffering—that opens a window on the real and is the main condition of the artistic experience, and Boredom ... that must be considered as the most tolerable because the most durable of human evils.”
—Samuel Beckett (1906–1989)