En la teoría de grafos , un etiquetado de grafos con bordes elegantes es un tipo de etiquetado de grafos . Este es un etiquetado para gráficos simples en el que no hay dos bordes distintos que conecten los mismos dos vértices distintos , ningún borde conecta un vértice consigo mismo y el gráfico está conectado . Sheng-Ping Lo introdujo por primera vez las etiquetas con bordes elegantes en su artículo seminal. [1]
Definición
Dado un gráfico G , denotamos el conjunto de aristas por y los vértices por . Sea q la cardinalidad dey p sea el de. Una vez que se da un etiquetado de los bordes, un vértice u del gráfico se etiqueta por la suma de las etiquetas de los bordes incidentes a él, módulo p . O, en símbolos, el etiquetado inducido en el vértice u viene dado por
donde V ( u ) es la etiqueta del vértice y E ( e ) es el valor asignado de una arista incidente a u .
El problema es encontrar un etiquetado para los bordes de modo que todas las etiquetas de 1 a q se usen una vez y las etiquetas inducidas en los vértices vayan de 0 a. En otras palabras, el conjunto resultante para las etiquetas de los bordes debe ser y para los vértices.
Se dice que un gráfico G es elegante en los bordes si admite un etiquetado elegante en los bordes.
Ejemplos de
Ciclos
Considere el ciclo con tres vértices, C 3 . Esto es simplemente un triángulo. Se pueden etiquetar los bordes 1, 2 y 3, y comprobar directamente que, junto con el etiquetado inducido en los vértices, se obtiene un etiquetado elegante en los bordes. Similar a los caminos,es elegante en los bordes cuando m es impar y no cuando m es par. [2]
Rutas
Considere un camino con dos vértices, P 2 . Aquí la única posibilidad es etiquetar el único borde en el gráfico 1. El etiquetado inducido en los dos vértices son ambos 1. Por lo tanto, P 2 no es elegante en los bordes.
Agregar una arista y un vértice a P 2 da P 3 , el camino con tres vértices. Denote los vértices por v 1 , v 2 y v 3 . Etiquete las dos aristas de la siguiente manera: la arista ( v 1 , v 2 ) está etiquetada como 1 y ( v 2 , v 3 ) etiquetada como 2. Las etiquetas inducidas en v 1 , v 2 y v 3 son entonces 1, 0 y 2 respectivamente. Este es un etiquetado elegante en los bordes y, por lo tanto, P 3 es elegante en los bordes.
Del mismo modo, se puede comprobar que P 4 no es elegante en los bordes.
En general, P m es elegante en los bordes cuando m es impar y no en los bordes cuando es par. Esto se deriva de una condición necesaria para la elegancia de los bordes.
Una condición necesaria
Lo dio una condición necesaria para que un gráfico sea elegante en los bordes. [1] Es que un gráfico con q aristas y p vértices tiene aristas agraciadas solo si
- es congruente con módulo p .
o, en símbolos,
Esto se conoce como condición de Lo en la literatura. [3] Esto se deriva del hecho de que la suma de las etiquetas de los vértices es el doble de la suma de las aristas, módulo p . Esto es útil para refutar un gráfico con bordes agraciados. Por ejemplo, se puede aplicar esto directamente a los ejemplos de ruta y ciclo dados anteriormente.
Otros resultados seleccionados
- El gráfico de Petersen no es elegante en los bordes.
- El gráfico de estrellas (un nodo central y m patas de longitud 1) tiene un borde elegante cuando m es par y no cuando m es impar . [4]
- El gráfico de la amistad es elegante en los bordes cuando m es impar y no cuando es par.
- Árboles regulares ,(profundidad n con cada nodo no hoja que emite m nuevos vértices) tienen bordes agraciados cuando m es par para cualquier valor n pero no bordes agraciados cuando m es impar. [5]
- El gráfico completo en n vértices,, es elegante en los bordes a menos que n sea uniforme por separado ,.
- El gráfico de escalera nunca es elegante en los bordes.
Referencias
- ↑ a b Lo, Sheng-Ping (1985). "En las etiquetas de gráficos Edge-Graceful". Congressus Numerantium . 50 : 231–241. Zbl 0597.05054 . Parámetro desconocido
|conference=
ignorado ( ayuda ) - ^ Q. Kuan, S. Lee, J. Mitchem y A. Wang (1988). "Gráficos unicíclicos de Edge-Graceful". Congressus Numerantium . 61 : 65–74.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ L. Lee, S. Lee y G. Murty (1988). "En las etiquetas de Edge-Graceful de gráficos completos: soluciones de la conjetura de Lo". Congressus Numerantium . 62 : 225-233.
- ^ D. Pequeño (1990). "Los gráficos de araña regulares (uniformes) tienen bordes agraciados". Congressus Numerantium . 74 : 247-254.
- ^ S. Cabaniss, R. Low, J. Mitchem (1992). "En árboles y gráficos regulares Edge-Graceful". Ars Combinatoria . 34 : 129-142.CS1 maint: varios nombres: lista de autores ( enlace )