×

On edge-graceful labelings of graphs. (English) Zbl 0597.05054

Proc. Conf., Sundance/Utah 1985, Congr. Numerantium 50, 231-241 (1985).
[For the entire collection see Zbl 0583.00003.]
This paper is a further one dealing with labeling graphs. The author considers edge-graceful graphs being defined as follows: A connected graph \(G=(V(G),E(G))\) is said to be edge-graceful if, and only if, there is an edge-labeling \(g: E\to \{1,2,...,| (G)| \}\) of \(G\) such that the weights \[ w_ g(v)=\sum_{e\in E(G), \;e \text{ incident to }v }g(e)\quad (\text{mod}| V(G)|) \] for each vertex \(v\in V(G)\) are consecutive integers ranging from 0 to \(| V(G)| -1\). Analogously to the theory of the graceful graphs the author derives some properties of edge- graceful graphs, proves a necessary condition for a graph to be edge- graceful, determines some classes of edge-graceful graphs, and finishes with the conjecture: Each complete graph \(K_ p\) \((p\geq 2)\) is edge-graceful.
Reviewer: R. Bodendiek

MSC:

05C99 Graph theory

Citations:

Zbl 0583.00003