Triangular embeddings of complete graphs from graceful labellings of paths

Goddyn, Luis; Richter, R. Bruce and Širáň, Jozef (2007). Triangular embeddings of complete graphs from graceful labellings of paths. Journal of Combinatorial Theory, Series B, 97(6) pp. 964–970.

DOI: https://doi.org/10.1016/j.jctb.2007.02.009

Abstract

We show that to each graceful labelling of a path on 2s+1 vertices, s≥2, there corresponds a current assignment on a 3-valent graph which generates at least 22s cyclic oriented triangular embeddings of a complete graph on 12s+7 vertices. We also show that in this correspondence, two distinct graceful labellings never give isomorphic oriented embeddings. Since the number of graceful labellings of paths on 2s+1 vertices grows asymptotically at least as fast as (5/3)2s, this method gives at least 11s distinct cyclic oriented triangular embedding of a complete graph of order 12s+7 for all sufficiently large s.

Viewing alternatives

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

Recommendations