8/18/14 Editar: Si alguien tiene una copia de una referencia relacionada, me encantaría verla. Por el momento, acepto la respuesta que figura a continuación y considero que la pregunta ha sido respondida afirmativamente: Sí .
Edición anterior: Parece que la respuesta es "sí", ya sea por una publicación ya existente o por la combinación de la referencia de Guo mencionada más abajo con la respuesta aquí (y una observación sobre los ciclos que admiten etiquetados graciosos). Pero no he podido localizar una referencia accesible, ¡y espero que alguien pueda encontrarla!
Nota: Perry Iverson señala que los gráficos descritos a continuación reciben diferentes nombres, y sugiere que ya existe una respuesta en la literatura. Yo añado un solicitud de referencia con la esperanza de que alguien pueda encontrar una prueba de la caracterización completa. De acuerdo con Gallian Un estudio dinámico del etiquetado de gráficos ( pdf ), hay algunos trabajos que se deben a Wenfu Guo, quien (por la cita que aparece a continuación) utiliza una notación similar a la mía, aunque se llamen dragones en lugar de globos .
Sin embargo, es evidente que la prueba a la que se alude a continuación no es bidireccional (o está mal planteada), ya que sólo discute los casos en los que el ciclo es congruente con $1$ o $2$ (mod $4$ ), pero el enfoque de Leen Droogendijk puede ampliarse para etiquetar con gracia $B(n,k)$ siempre que $n \equiv 0$ o $3$ (mod $4$ ); ¡precisamente los casos complementarios! Además, la imagen de Wikipedia muestra claramente un etiquetado elegante en el que el ciclo es congruente con $3$ (mod $4$ ).
Aceptaré con gusto una respuesta con una versión accesible del trabajo de Guo (o de cualquier otra persona que haya logrado una caracterización de tales gráficos).
La página web sobre etiquetados elegantes incluye el siguiente diagrama:
Citando la página:
En la teoría de grafos, un etiquetado elegante de un gráfico con $m$ aristas es un etiquetado de sus vértices con algún subconjunto de los enteros entre $0$ y $m$ inclusive, de forma que no haya dos vértices que compartan una etiqueta, y que cada arista se identifique de forma única por la diferencia positiva o absoluta entre sus puntos extremos.
Llamemos a un gráfico a globo si consiste en un $n$ -ciclo con una sola hebra ( cadena ) que emana de uno de los vértices del mencionado ciclo. Además, exigimos que el componente del globo tenga $n \geq 3$ vértices y el componente de la cadena para tener un $k \geq 1$ vértices; en tal caso, denotamos el globo como $B(n,k)$ .
Por ejemplo, el diagrama anterior muestra $B(3,2)$ es decir, un globo con un $3$ -(los vértices etiquetados como $0, 4, 5$ constituyen el componente del globo) y una longitud $2$ cadena (que emana del vértice $0$ ).
Es un hecho: Para todos $k \geq 1$ el globo $B(3,k)$ admite un etiquetado elegante.
( Prueba: De la izquierda al lector).
Pregunta: ¿Qué globos admiten graciosos etiquetados?
Por ejemplo, ¿puede alguien demostrar que $B(4,k)$ admite un etiquetado elegante para todos $k \geq 1$ ?
Como alternativa, ¿alguien puede proponer una $n \geq 3$ y $k \geq 1$ para lo cual $B(n,k)$ hace no ¿admitir un etiquetado elegante?
Unas palabras de advertencia: La conjetura de que todos los árboles admiten graciosos etiquetados es un problema abierto notoriamente difícil. (Para un post relacionado con MSE, véase aquí .) Idealmente, desearía una caracterización completa de la gracia de los globos; sin embargo, ciertamente votaré las respuestas con contribuciones no triviales (y puede que simplemente "acepte" una, particularmente si la pregunta aquí puede transformarse en una que implique la conjetura para los árboles).
