Sesión Matemática Discreta

Diciembre 14, 12:00 ~ 12:20

Sobre distintas familias de digrafos (h,j)-adjuntos y sus energías

Braicovich, Teresa

Dentro de los temas relevantes referidos a la algebrización de los grafos y digrafos se pueden mencionar la adjunción, el espectro y la energía. Dentro de la adjunción, consideramos los digrafos $(h, j)$-adjuntos,$^{h,j}G$, cuyos vértices son los caminos de longitud $h$ del digrafo $G$ y cuya relación de precedencia está definida por: $y \in \ \ ^{h,j}G_{(X)}$ si y sólo si el $j$-subcamino final de $x$ coincide con el $j$-subcamino inicial de $y$ (no necesariamente $x \not= y$ ).\\ Partiendo de la caracterización, en términos generales, que hemos realizado, en función de los parámetros $n$, $h $ y $j$ de los digrafos $(h,j)$-adjuntos de los paths $P_n$ y de los ciclos $C_n$, se presentarán los $(h, j)$-adjuntos de otras familias de digrafos, como son las ruedas $R_n$, los barriletes $B_{ab}$ y algunos árboles particulares, entre ellos los árboles binarios completos $A_p$ en el que todas las hojas tienen igual profundidad $p$.\\ En primer lugar se dan las caracterizaciones de Paths y Ciclos:\\ -El digrafo $(h,j)$-adjunto de $P_n$ es de orden $(n-h)$ y es la unión de $(h-j)$ componentes conexas. Sea $d$ el cociente y $r$ el resto de la división entre $(n-h)$ y $(h-j)$, el digrafo $(h,j)$-adjunto de $P_n$ es la unión de $(h-j-r)$ componentes conexas $P_d$ y $r$ componentes conexas $P_d+1$.\\ -tEl digrafo $(h, j)$-adjunto del ciclo $C_n$ es de orden $n$ e igual a la unión de $d$ componentes conexas iguales, siendo $d$ el máximo común divisor (MCD) entre los valores $n$ y $(h-j)$ y el orden de cada una de las componentes es igual al cociente entre los valores $n$ y $d$.\\ A partir de lo mencionado y considerando que las familias de ruedas, barriletes y árboles pueden obtenerse como unión de Paths y Ciclos, se presentan las siguientes caracterizaciones:\\ - Las ruedas $R_n$ son digrafos que se obtienen a partir de un ciclo $C_{n-1}$ y un vértice del cual sale (entra) un arco hacia (desde) cada vértice del ciclo. Tomando $t=n-1$, se tiene que los $(h,j)$-adjuntos son de tamaño y de orden igual a $2t$, y están compuestos por un subgrafo $(h,j)$-adjunto de $C_t$ y $t$ vértices de grado positivo (negativo) y $t$ arcos puentes que tienen como extremo final (inicial) a los vértices del $(h,j)$-adjunto de $C_t$.\\ - Los barriletes $B_{ab}$ resultan de la unión de un ciclo $C_b$ y un path $P_a$ con un único vértice común. Los $(h,j)$-adjuntos de los $B_{ab}$ se constituyen a partir de la unión de los $(h,j)$-adjuntos del path $P_{a+h-1}$ y el ciclo $C_b$ correspondientes, con el anexo de arcos que van desde un vértice de uno a un vértice del otro subgrafo.\\ - Los $(h,j)$-adjuntos de los árboles binarios $A_p$ poseen orden $(n-\sum_{i=1}^{h-1} 2^{i-1})$ y se forman de acuerdo a las relaciones entre $h, j$ y $p$ y según las caracterizaciones de los Paths.\\ A partir de lo anteriormente citado se encontraron algunas regularidades para la energía de dichos digrafos. Una de ellas referida a la relación existente entre la energía del digrafo $(h,j)$-adjunto y la suma de las energías de sus componentes conexas. Es sabido que la energía ordinaria coincide con la suma de las energías de sus componentes conexas, pero en el caso de la energía laplaciana no siempre es así.\\ Referencias bibliográficas:\\ Chiappa, R., (1982) Palabras circulares equilibradas. Grafos Adjuntos. INMABB CONICET. Universidad Nacional del Sur. \\ Brouser, A.; Haemers, W. (2011) Spectra of graphs. Ed.Springer.\\ Gutman, I; Zhou, B (2006). Laplacian energy of a graph. Linear Algebra and its applications 414. 29-37.\\

Autores: Braicovich, Teresa / Cognigni, Raquel.