Etiquetado elegante en los bordes

En teoría de grafos , un etiquetado de bordes elegantes es un tipo de etiquetado de gráficos para gráficos simples y conectados en los que no hay dos aristas distintas que conecten los mismos dos vértices distintos y ninguna arista conecta un vértice consigo misma.

Los etiquetados con bordes elegantes fueron introducidos por primera vez por Sheng-Ping Lo en su artículo fundamental. ^[1]

Definición

Dado un gráfico $G$ , denotamos el conjunto de sus aristas por $E (G)$ y el de sus vértices por $V (G)$ . Sea $q$ la cardinalidad de $E (G)$ yp $la$ de $V (G)$ . Una vez que se asigna un etiquetado de los bordes, un vértice del gráfico se etiqueta mediante la suma de las etiquetas de los bordes incidentes sobre él, módulo $p$ . O, en símbolos, el etiquetado inducido en un vértice viene dado por

V(u)=\Sigma E(e)\mod |V(G)|

donde $V (u)$ es el valor resultante para el vértice $u$ y $E (e)$ es el valor existente de una arista $e$ incidente en $u$ .

El problema es encontrar un etiquetado para los bordes tal que todas las etiquetas de $1$ a $q$ se usen una vez y que las etiquetas inducidas en los vértices vayan de $0$ a $p - 1$ . En otras palabras, el conjunto resultante de etiquetas para los bordes debe ser ${1, 2,..., q}$ , cada valor se usa una vez, y el de los vértices debe ser ${0, 1,..., p - 1}$ .

Se dice que un gráfico $G$ tiene bordes elegantes si admite un etiquetado con bordes elegantes.

Ejemplos

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, esto proporciona un etiquetado elegante en los bordes. De manera similar a los caminos, $C m$ tiene bordes elegantes cuando $m$ es impar y no cuando $m$ es par. ^[2]

Caminos

Considere un camino con dos vértices, $P 2$ . Aquí la única posibilidad es etiquetar el único borde en el gráfico como 1. El etiquetado inducido en los dos vértices es ambos 1. Por lo tanto, $P 2$ no tiene bordes elegantes.

Al agregar una arista y un vértice a $P 2$ se obtiene $P 3$ , el camino con tres vértices. Denota los vértices por $v 1$ , $v 2$ y $v 3$ . Etiquete los dos bordes de la siguiente manera: el borde $(v 1, v 2)$ está etiquetado como 1 y $(v 2, v 3)$ está etiquetado como 2. Los etiquetados inducidos en $v 1$ , $v 2$ y $v 3$ son entonces 1, 0 y 2 respectivamente. Este es un etiquetado con bordes elegantes, por lo que $P 3$ tiene bordes elegantes.

De manera similar, se puede comprobar que $P 4$ no tiene bordes elegantes.

En general, $P m$ tiene bordes elegantes cuando $m$ es impar y no bordes elegantes cuando es par. Esto se desprende 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 con $q$ aristas y $p$ vértices tenga bordes elegantes: ^[1] $q (q + 1)$ debe ser congruente con $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠pag ( pag – 1)/2⁠ mod p$ . En símbolos:

q(q+1)\equiv {\frac {p(p-1)}{2}}\mod p.

En la literatura esto se conoce como condición de Lo . ^[3] Esto se desprende 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 que un gráfico tiene bordes elegantes. Por ejemplo, se puede aplicar esto directamente a los ejemplos de rutas y ciclos dados anteriormente.

Otros resultados seleccionados

El gráfico de Petersen no tiene bordes elegantes.
El gráfico estelar (un nodo central y m catetos de longitud 1) tiene bordes elegantes cuando m es par y no cuando m es impar . ^[4] $S_{m}$
El gráfico de la amistad tiene bordes elegantes cuando m es impar y no cuando es par. $F_{m}$
Los árboles regulares ( profundidad n con cada nodo que no es hoja emitiendo m nuevos vértices) tienen bordes elegantes cuando m es par para cualquier valor n, pero no tienen bordes elegantes cuando m es impar. ^[5] $T_{m,n}$
El gráfico completo en n vértices, , tiene bordes elegantes a menos que n sea sencillamente par , . ${\ Displaystyle K_ {n}}$ $n=2\mod 4$
El gráfico de escalera nunca tiene bordes elegantes.

Referencias

^ ab Lo, Sheng-Ping (1985). "Etiquetados de gráficos elegantes en los bordes". Congreso Numerantium . Conferencia de Sundance, Utah. vol. 50, págs. 231-241. Zbl 0597.05054.
^ Q. Kuan, S. Lee, J. Mitchem y A. Wang (1988). "En gráficos unicíclicos elegantes de borde". Congreso Numerantium . 61 : 65–74.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
^ L. Lee, S. Lee y G. Murty (1988). "Sobre etiquetado elegante de gráficos completos: soluciones de la conjetura de Lo". Congreso Numerantium . 62 : 225–233.
^ D. Pequeño (1990). "Los gráficos de araña normales (pares) tienen bordes elegantes". Congreso Numerantium . 74 : 247–254.
^ S. Cabaniss, R. Low, J. Mitchem (1992). "En árboles y gráficos regulares elegantes en los bordes". Ars Combinatoria . 34 : 129-142.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )