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:
“Manners are of such great consequence to the novelist that any kind will do. Bad manners are better than no manners at all, and because we are losing our customary manners, we are probably overly conscious of them; this seems to be a condition that produces writers.”
—Flannery O’Connor (1925–1964)