Graceful labeling

Last updated December 12, 2024

In graph theory, a graceful labeling of a graph with $m$ edges is a labeling of its vertices with some subset of the integers from 0 to $m$ inclusive, such that no two vertices share a label, and each edge is uniquely identified by the absolute difference between its endpoints, such that this magnitude lies between 1 and $m$ inclusive.^[1] A graph which admits a graceful labeling is called a graceful graph.

A major open problem in graph theory is the graceful tree conjecture or Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, and sometimes abbreviated GTC (not to be confused with Kotzig's conjecture on regularly path connected graphs).^[3] It hypothesizes that all trees are graceful. It is still an open conjecture, although a related but weaker conjecture known as "Ringel's conjecture" was partially proven in 2020.^[4]^[5]^[6] Kotzig once called the effort to prove the conjecture a "disease".^[7]

Another weaker version of graceful labelling is near-graceful labeling, in which the vertices can be labeled using some subset of the integers on $[0, m + 1]$ such that no two vertices share a label, and each edge is uniquely identified by the absolute difference between its endpoints (this magnitude lies on $[1, m + 1]$ ).

Another conjecture in graph theory is Rosa's conjecture, named after Alexander Rosa, which says that all triangular cacti are graceful or nearly-graceful.^[8]

A graceful graph with edges 0 to $m$ is conjectured to have no fewer than $\left\lceil {\sqrt {3m+{\tfrac {9}{4}}}}\right\rfloor$ vertices, due to sparse ruler results. This conjecture has been verified for all graphs with 213 or fewer edges. A related conjecture is that the smallest 2 $m$ -valence graceful graph has $3m^{2}$ edges, with the case for 6-valence shown below.

A graceful graph with 27 edges and 9 vertices Toroidal6.png — A graceful graph with 27 edges and 9 vertices

Selected results

In his original paper, Rosa proved that an Eulerian graph with number of edges m ≡ 1 (mod 4) or m ≡ 2 (mod 4) cannot be graceful.^[2]
Also in his original paper, Rosa proved that the cycle C_n is graceful if and only if n ≡ 0 (mod 4) or n ≡ 3 (mod 4).
All path graphs and caterpillar graphs are graceful.^[2]
All lobster graphs with a perfect matching are graceful.^[9]
All trees with at most 27 vertices are graceful; this result was shown by Aldred and McKay in 1998 using a computer program.^[10]^[11] This was extended to trees with at most 29 vertices in the Honours thesis of Michael Horton.^[12] Another extension of this result up to trees with 35 vertices was claimed in 2010 by the Graceful Tree Verification Project, a distributed computing project led by Wenjie Fang.^[13]
All wheel graphs, web graphs, helm graphs, gear graphs, and rectangular grids are graceful.^[10]
All n-dimensional hypercubes are graceful.^[14]
All simple connected graphs with four or fewer vertices are graceful. The only non-graceful simple connected graphs with five vertices are the 5-cycle (pentagon); the complete graph K₅; and the butterfly graph.^[15]

Related Research Articles

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges.

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

In mathematics, a universal graph is an infinite graph that contains every finite graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or random graph. More recent work has focused on universal graphs for a graph family $F$ : that is, an infinite graph belonging to F that contains all finite graphs in $F$ . For instance, the Henson graphs are universal in this sense for the $i$ -clique-free graphs.

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, 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.

<span class="mw-page-title-main">Circulant graph</span> Undirected graph acted on by a vertex-transitive cyclic group of symmetries

In graph theory, a circulant graph is an undirected graph acted on by a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a cyclic graph, but this term has other meanings.

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 graph theory, the crossing number $cr(G)$ of a graph $G$ is the lowest number of edge crossings of a plane drawing of the graph $G$ . For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

In the mathematics of graph drawing, Turán's brick factory problem asks for the minimum number of crossings in a drawing of a complete bipartite graph. The problem is named after Pál Turán, who formulated it while being forced to work in a brick factory during World War II.

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.

Anton Kotzig was a Slovak–Canadian mathematician, expert in statistics, combinatorics and graph theory.

Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.

In graph theory, a partial cube is a graph that is an isometric subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

In polyhedral combinatorics, a stacked polytope is a polytope formed from a simplex by repeatedly gluing another simplex onto one of its facets.

<span class="mw-page-title-main">Oberwolfach problem</span>

In mathematics, the Oberwolfach problem is an open problem that may be formulated either as a problem of scheduling seating assignments for diners, or more abstractly as a problem in graph theory, on the edge cycle covers of complete graphs. It is named after the Oberwolfach Research Institute for Mathematics, where the problem was posed in 1967 by Gerhard Ringel. It is known to be true for all sufficiently-large complete graphs.

<span class="mw-page-title-main">Kotzig's theorem</span>

In graph theory and polyhedral combinatorics, areas of mathematics, Kotzig's theorem is the statement that every polyhedral graph has an edge whose two endpoints have total degree at most 13. An extreme case is the triakis icosahedron, where no edge has smaller total degree. The result is named after Anton Kotzig, who published it in 1955 in the dual form that every convex polyhedron has two adjacent faces with a total of at most 13 sides. It was named and popularized in the west in the 1970s by Branko Grünbaum.

The Earth–Moon problem is an unsolved problem on graph coloring in mathematics. It is an extension of the planar map coloring problem, and was posed by Gerhard Ringel in 1959. An intuitive form of the problem asks how many colors are needed to color political maps of the Earth and Moon, in a hypothetical future where each Earth country has a Moon colony which must be given the same color. In mathematical terms, it seeks the chromatic number of biplanar graphs. It is known that this number is at least 9 and at most 12.

Kotzig's conjecture is an unproven assertion in graph theory which states that finite graphs with certain properties do not exist. A graph is a $-graph if each pair of distinct vertices is connected by exactly one path of length . Kotzig's conjecture asserts that for there are no finite -graphs with two or more vertices. The conjecture was first formulated by Anton Kotzig in 1974. It has been verified for, but remains open in the general case.$

References

↑ Virginia Vassilevska, "Coding and Graceful Labeling of trees." SURF 2001. PostScript
1 2 3 Rosa, A. (1967), "On certain valuations of the vertices of a graph", Theory of Graphs (Internat. Sympos., Rome, 1966), New York: Gordon and Breach, pp. 349–355, MR 0223271 .
↑ Wang, Tao-Ming; Yang, Cheng-Chang; Hsu, Lih-Hsing; Cheng, Eddie (2015), "Infinitely many equivalent versions of the graceful tree conjecture", Applicable Analysis and Discrete Mathematics, 9 (1): 1–12, doi: 10.2298/AADM141009017W , MR 3362693
↑ Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2020). "A proof of Ringel's Conjecture". arXiv: 2001.02665 [math.CO].
↑ Huang, C.; Kotzig, A.; Rosa, A. (1982), "Further results on tree labellings", Utilitas Mathematica, 21: 31–48, MR 0668845 .
↑ Hartnett, Kevin. "Rainbow Proof Shows Graphs Have Uniform Parts". Quanta Magazine. Retrieved 2020-02-29.
↑ Huang, C.; Kotzig, A.; Rosa, A. (1982), "Further results on tree labellings", Utilitas Mathematica, 21: 31–48, MR 0668845 .
↑ Rosa, A. (1988), "Cyclic Steiner Triple Systems and Labelings of Triangular Cacti", Scientia, 1: 87–95.
↑ Morgan, David (2008), "All lobsters with perfect matchings are graceful", Bulletin of the Institute of Combinatorics and Its Applications, 53: 82–85, hdl:10402/era.26923 .
1 2 Gallian, Joseph A. (1998), "A dynamic survey of graph labeling", Electronic Journal of Combinatorics, 5: Dynamic Survey 6, 43 pp. (389 pp. in 18th ed.) (electronic), MR 1668059 .
↑ Aldred, R. E. L.; McKay, Brendan D. (1998), "Graceful and harmonious labellings of trees", Bulletin of the Institute of Combinatorics and Its Applications, 23: 69–72, MR 1621760 .
↑ Horton, Michael P. (2003), Graceful Trees: Statistics and Algorithms .
↑ Fang, Wenjie (2010), A Computational Approach to the Graceful Tree Conjecture, arXiv: 1003.3045 , Bibcode:2010arXiv1003.3045F . See also Graceful Tree Verification Project
↑ Kotzig, Anton (1981), "Decompositions of complete graphs into isomorphic cubes", Journal of Combinatorial Theory, Series B, 31 (3): 292–296, doi: 10.1016/0095-8956(81)90031-9 , MR 0638285 .
↑ Weisstein, Eric W. "Graceful graph". MathWorld .

Graceful labeling

Contents

Selected results

See also

Related Research Articles

References

External links

Further reading