The Fascinating World of Graph Theory by Benjamin Arthur. Zhang Ping Chartrand Gary

Author:Benjamin, Arthur.,Zhang, Ping,Chartrand, Gary.
Language: eng
Format: epub, pdf
Publisher: Princeton University Press
Published: 2014-07-14T16:00:00+00:00

for each edge uv of G.

Not only is the complete graph K3 of order 3 graceful (as shown in Figure 8.4), so too is K4. However, such is not the case for K5.

Figure 8.4. Three graceful graphs.

Figure 8.5. Showing that K5 is not graceful.

Example 8.5: The complete graph K5 is not graceful.

SOLUTION:

If K5 were graceful, then because the size of K5 is 10, it would be possible to label the vertices with five of the integers 0, 1, …, 10 in such a way that the edges are labeled 1, 2, …, 10. In particular, five edges of K5 must be labeled with the odd integers 1, 3, 5, 7, 9. The only way that an edge uv of K5 can be labeled with an odd integer is for one of u and v to be labeled with an odd integer and the other to be labeled with an even integer (see Figure 8.5). If all five vertices of K5 are labeled with odd integers (or even integers), then no edge has an odd label. If exactly one vertex of K5 has an odd label (or an even label), then exactly four edges receive an odd label. If exactly two vertices of K5 have odd labels (or even labels), then exactly six edges receive an odd label. Therefore, it is not possible to label the vertices so that exactly five edges are labeled with odd integers.

♦

While many questions exist concerning which graphs are graceful, there is one well-known class of graphs, every member of which is believed to be graceful. The following conjecture is due to Gerhard Ringel and Anton Kotzig, who was the doctoral advisor of Alexander Rosa.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.