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:
“Undoubtedly we have not questions to ask which are unanswerable. We must trust the perfection of the creation so far, as to believe that whatever curiosity the order of things has awakened in our minds, the order of things can satisfy. Every man’s condition is a solution in hieroglyphic to those inquiries he would put. He acts it as life, before he apprehends it as truth.”
—Ralph Waldo Emerson (1803–1882)