Edge-graceful labeling

Last updated March 28, 2024

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.

Definition

Given a graph $G$ , we denote the set of its edges by $E (G)$ and that of its 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 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 a vertex is given by

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

where $V (u)$ is the resulting value for the vertex $u$ and $E (e)$ is the existing value of an edge $e$ 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 that the induced labels on the vertices run from $0$ to $p - 1$ . In other words, the resulting set of labels for the edges should be ${1, 2, \dots, q}$ , each value being used once, and that for the vertices should be ${0, 1, \dots, p - 1}$ .

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

Examples

Cycles

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{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);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.

Related Research Articles

In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Graph (discrete mathematics)</span> Vertices connected in pairs by edges

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

In graph theory, two graphs $and are homeomorphic if there is a graph isomorphism from some subdivision of to some subdivision of . If the edges of a graph are thought of as lines drawn from one vertex to another, then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the topological sense.$

In graph theory, a cograph, or complement-reducible graph, or P₄-free graph, is a graph that can be generated from the single-vertex graph K₁ by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K₁ and is closed under complementation and disjoint union.

In the mathematical field of graph theory, a graph $G$ is symmetric if, given any two pairs of adjacent vertices $u 1 — v 1$ and $u 2 — v 2$ of $G$ , there is an automorphism

In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph.

In graph theory, a domatic partition of a graph $is a partition of into disjoint sets,,..., such that each V i is a dominating set for G . The figure on the right shows a domatic partition of a graph; here the dominating set consists of the yellow vertices, consists of the green vertices, and consists of the blue vertices.$

The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the countries of the world, the regions may be colored using no more than five colors in such a way that no two adjacent regions receive the same color.

In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex $can reach a vertex if there exists a sequence of adjacent vertices which starts with and ends with .$

Graph pebbling is a mathematical game played on a graph with zero or more pebbles on each of its vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of choosing a vertex with at least two pebbles, removing two pebbles from it, and adding one to an adjacent vertex (the second removed pebble is discarded from play). π(G), the pebbling number of a graph G, is the lowest natural number n that satisfies the following condition:

Given any target or 'root' vertex in the graph and any initial configuration of n pebbles on the graph, it is possible, after a possibly-empty series of pebbling moves, to reach a new configuration in which the designated root vertex has one or more pebbles.

In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex identification is a less restrictive form of this operation.

<span class="mw-page-title-main">Handshaking lemma</span> Every graph has evenly many odd vertices

In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or in which every block is an edge or a cycle.

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph $, find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph .$

In the mathematical field of graph theory, the friendship graph $F n$ is a planar, undirected graph with $2 n + 1$ vertices and $3 n$ edges.

In the mathematical field of graph theory, the windmill graph $Wd(k, n)$ is an undirected graph constructed for $k \geq 2$ and $n \geq 2$ by joining $n$ copies of the complete graph $K k$ at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs.

In graph theory, interval edge coloring is a type of edge coloring in which edges are labeled by the integers in some interval, every integer in the interval is used by at least one edge, and at each vertex the labels that appear on incident edges form a consecutive set of distinct numbers.

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.

References

1 2 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 page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[lo-1] 1 2 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)

[1]

[2]

[3]

[4]

[5]