A counterexample to a conjecture of Ghosh

zbMATH Open1334.05143arXiv1412.6984MaRDI QIDQ2799696

Elliot Krop, Hung Hua, Christopher Raridan

Publication date: 13 April 2016

Published in: Bulletin of the Institute of Combinatorics and its Applications (Search for Journal in Brave)

Abstract: We answer two questions of Shamik Ghosh 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.

Full work available at URL: https://arxiv.org/abs/1412.6984

zbMATH Keywords

graceful labeling graceful tree conjecture lobster Bermond's conjecture

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78)