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:
“I would fain say something, not so much concerning the Chinese and Sandwich Islanders as you who read these pages, who are said to live in New England; something about your condition, especially your outward condition or circumstances in this world, in this town, what it is, whether it is necessary that it be as bad as it is, whether it cannot be improved as well as not.”
—Henry David Thoreau (1817–1862)