For k ∈ ℤ+ and G a simple, connected graph, a k-radio labeling f : V (G) → ℤ+ of G requires all pairs of distinct vertices u and v to satisfy |f(u) − f(v)| ≥ k + 1 − d(u, v). We consider k-radio labelings of G when k = diam(G). In this setting, f is injective; if f is also surjective onto {1, 2, . . . , |V (G)|}, then f is a consecutive radio labeling. Graphs that can be labeled with such a labeling are called radio graceful. In this paper, we give two results on the existence of radio graceful Hamming graphs. The main result shows that the Cartesian product of t copies of a complete graph is radio graceful for certain t. Graphs of this form provide infinitely many examples of radio graceful graphs of arbitrary diameter. We also show that these graphs are not radio graceful for large t.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Hanoi graphs H pn model the Tower of Hanoi game with p pegs and n discs. Sierpinski graphs S pn arose in investigations of universal topological spaces and have meanwhile been studied extensively. It is proved that S pn embeds as a spanning subgraph into H pn if and only if p is odd or, trivially, if n = 1.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.