Sobre Rotulações L(h, k) de Caterpillars

Uma rotulação L(h, k) é uma atribuição σ de inteiros aos vértices de um grafo simples tal que os rótulos de: vértices adjacentes diferem de pelo menos h; vértices com um vizinho em comum diferem de pelo menos k. A maior diferença entre os rótulos de quaisquer dois vértices é o span de σ. Determinar o L(h, k)-span, i.e. o menor span para todas as rotulações σ, é NP-difı́cil para árvores. Caterpillars são uma subclasse das árvores muito estudada no contexto de problemas rotulação. Nós provamos limitantes justos para o L(h, k)-span de todo caterpillar G, determinando o valor exato se k divide h e G tem no máximo sete vértices em um caminho máximo.