Edge-graceful labeling

In graph theory, an edge-graceful labeling is a type of graph labeling for simple, connected graphs in which no two distinct edges connect the same two distinct vertices and no edge connects a vertex to itself.

Edge-graceful labelings were first introduced by Sheng-Ping Lo in his seminal paper.[1]

Definition

Given a graph $G$ , we denote the set of edges by $E (G)$ and the vertices by $V (G)$ . Let $q$ be the cardinality of $E (G)$ and $p$ be that of $V (G)$ . Once a labeling of the edges is given, a vertex $u$ of the graph is labeled by the sum of the labels of the edges incident to it, modulo $p$ . Or, in symbols, the induced labeling on the vertex $u$ is given by

V(u)=\Sigma E(e)\mod |V(G)|

where $V (u)$ is the label for the vertex and $E (e)$ is the assigned value of an edge incident to $u$ .

The problem is to find a labeling for the edges such that all the labels from 1 to $q$ are used once and the induced labels on the vertices run from 0 to $p - 1$ . In other words, the resulting set for labels of the edges should be ${1, 2, \dots, q}$ and ${0, 1, \dots, p - 1}$ for the vertices.

A graph $G$ is said to be edge-graceful if it admits an edge-graceful labeling.

Examples

Cycles

An edge-graceful labeling of

C 5

Consider the cycle with three vertices, $C 3$ . This is simply a triangle. One can label the edges 1, 2, and 3, and check directly that, along with the induced labeling on the vertices, this gives an edge-graceful labeling. Similar to paths, $C m$ is edge-graceful when $m$ is odd and not when $m$ is even.[2]

Paths

Consider a path with two vertices, $P 2$ . Here the only possibility is to label the only edge in the graph 1. The induced labeling on the two vertices are both 1. So $P 2$ is not edge-graceful.

Appending an edge and a vertex to $P 2$ gives $P 3$ , the path with three vertices. Denote the vertices by $v 1$ , $v 2$ , and $v 3$ . Label the two edges in the following way: the edge $(v 1, v 2)$ is labeled 1 and $(v 2, v 3)$ labeled 2. The induced labelings on $v 1$ , $v 2$ , and $v 3$ are then 1, 0, and 2 respectively. This is an edge-graceful labeling and so $P 3$ is edge-graceful.

Similarly, one can check that $P 4$ is not edge-graceful.

In general, $P m$ is edge-graceful when $m$ is odd and not edge-graceful when it is even. This follows from a necessary condition for edge-gracefulness.

A necessary condition

Lo gave a necessary condition for a graph with $q$ edges and $p$ vertices to be edge-graceful:[1] $q (q + 1)$ must be congruent to $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}p(p – 1)/2 mod p$ . In symbols:

q(q+1)\equiv {\frac {p(p-1)}{2}}\mod p.

This is referred to as Lo's condition in the literature.[3] 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.

Further selected results

The Petersen graph is not edge-graceful.
The star graph $S_{m}$ (a central node and m legs of length 1) is edge-graceful when m is even and not when m is odd.[4]
The friendship graph $F_{m}$ is edge-graceful when m is odd and not when it is even.
Regular trees, $T_{m,n}$ (depth n with each non-leaf node emitting m new vertices) are edge-graceful when m is even for any value n but not edge-graceful whenever m is odd.[5]
The complete graph on n vertices, $K_{n}$ , is edge-graceful unless n is singly even, $n=2\mod 4$ .
The ladder graph is never edge-graceful.

References

Lo, Sheng-Ping (1985). "On Edge-Graceful Labelings of Graphs". Congressus Numerantium. Sundance Conference, Utah. Vol. 50. pp. 231–241. Zbl 0597.05054.
Q. Kuan, S. Lee, J. Mitchem, and A. Wang (1988). "On Edge-Graceful Unicyclic Graphs". Congressus Numerantium. 61: 65–74.{{cite journal}}: CS1 maint: multiple names: authors list (link)
L. Lee, S. Lee and G. Murty (1988). "On Edge-Graceful Labelings of Complete Graphs: Solutions of Lo's Conjecture". Congressus Numerantium. 62: 225–233.
D. Small (1990). "Regular (even) Spider Graphs are Edge-Graceful". Congressus Numerantium. 74: 247–254.
S. Cabaniss, R. Low, J. Mitchem (1992). "On Edge-Graceful Regular Graphs and Trees". Ars Combinatoria. 34: 129–142.{{cite journal}}: CS1 maint: multiple names: authors list (link)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[lo-1] Lo, Sheng-Ping (1985). "On Edge-Graceful Labelings of Graphs". Congressus Numerantium. Sundance Conference, Utah. Vol. 50. pp. 231–241. Zbl 0597.05054.

[2] Q. Kuan, S. Lee, J. Mitchem, and A. Wang (1988). "On Edge-Graceful Unicyclic Graphs". Congressus Numerantium. 61: 65–74.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[3] L. Lee, S. Lee and G. Murty (1988). "On Edge-Graceful Labelings of Complete Graphs: Solutions of Lo's Conjecture". Congressus Numerantium. 62: 225–233.

[4] D. Small (1990). "Regular (even) Spider Graphs are Edge-Graceful". Congressus Numerantium. 74: 247–254.

[5] S. Cabaniss, R. Low, J. Mitchem (1992). "On Edge-Graceful Regular Graphs and Trees". Ars Combinatoria. 34: 129–142.{{cite journal}}: CS1 maint: multiple names: authors list (link)