A counterexample to a conjecture of Ghosh. (English) Zbl 1334.05143

Hua, Hung; Krop, Elliot; Raridan, Christopher

Bull. Inst. Comb. Appl. 75, 79-82 (2015).

Summary: We answer two questions of S. Ghosh [“On certain classes of graceful lobsters”, Preprint, arXiv:1306.2932] in the negative. We show that there exists a lobster tree of diameter less than 6 which accepts no alpha-labeling with two central vertices labeled by the critical number and the maximum vertex label. We also show a simple example of a tree of diameter 4, with an even degree central vertex which does not accept a maximum label in any graceful labeling.

MSC:

05C78

Graph labelling (graceful graphs, bandwidth, etc.)

Keywords:

graceful labeling; graceful tree conjecture; Bermond’s conjecture; lobster