Resumen de Cotas de diversos parámetros de un grafo a partir de los autovalores de su matriz laplaciana

Juan Alberto Rodríguez Velázquez

• ESTE TRABAJO SE ENMARCA DENTRO DE LA TEORIA ALGEBRAICA DE GRAFOS, EN PARTICULAR, EN LA TEORIA ESPECTRAL DE GRAFOS, FORMA PARTE DE UN AMPLIO PROYECTO QUE ESTUDIA QUE INFORMACION SE PUEDE OBTENER DE UN GRAFO A PARTIR DE LOS AUTOVALORES DE SU MATRIZ DE ADYACENCIA O DE SU MATRIZ LAPLACIANA.

  SE OBTIENEN COTAS DE VARIOS PARAMETROS DE UN GRAFO EN FUNCION DE LOS AUTOVALORES DE SU MATRIZ LAPLACIANA. EN PARTICULAR, SE EXTIENDEN AL CASO DE LA MATRIZ LAPLACIANA LOS TRABAJOS PREVIOS CON LA MATRIZ DE ADYACENCIA Y SE COMPARAN AMBOS METODOS. UN DETALLE MAYOR APARECE A CONTINUACION AL INDICAR LOS RESULTADOS OBTENIDOS.

  CON EL OBJETIVO DE OBTENER COTAS DE ALGUNOS PARAMETROS, DESDE EL PUNTO DE VISTA LOCAL, SE EXTIENDE EL CONCEPTO DE ESPECTRO LOCAL DE UN GRAFO A UNA MATRIZ SIMETRICA DONDE EL ESTUDIO LOCAL SE HACE RESPECTO A UN VECTOR. DESPUES SE PARTICULARIZA AL CASO EN QUE LA MATRIZ ES LA LAPLACIANA DEL GRAFO Y EL ESTUDIO LOCAL SE HACE RESPECTO A UN CONJUNTO H DE VERTICES. EL ESPECTRO QUE RESULTA DE DICHO ESTUDIO ES DENOMINADO H-ESPECTRO LAPLACIANO DEL GRAFO.

  SE OBTIENEN NUEVAS COTAS SUPERIORES PARA EL EXCESO DE ORDEN K DE TODO CONJUNTO DE VERTICES DE UNA DETERMINADA CARDINALIDAD, SE GENERALIZAN ALGUNOS DE LOS RESULTADOS EXISTENTES RELACIONADOS CON EL EXCESO Y SE OBTIENE EL ANALOGO LAPLACIANO DE OTROS. SE OBTIENE, ADEMAS, UNA COTA PARA EL EXCESO DE UN GRAFO CAMINO-REGULAR EN LA QUE SE INVOLUCRA TODO EL ESPECTRO LAPLACIANO. SE OBTIENEN COTAS, DESDE EL PUNTO DE VISTA LOCAL, PARA EL EXCESO DE UN CONJUNTO DE VERTICES. SE PROPONEN VARIAS COTAS PARA LA DISTANCIA MEDIA DE UN GRAFO A PARTIR DE LAS COTAS DEL EXCESO.

  SE DEFINE Y ACOTA INFERIORMENTE LA CONSTANTE DE AUMENTO DE ORDEN K EN UN GRAFO Y, COMO CASO PARTICULAR DE ESTA, SE OBTIENE UNA COTA PARA LA CONSTANTE DE AUMENTO QUE EN DETERMINADOS CASOS MEJORA LA COTA DE N. ALON. SE ACOTA INFERIORMENTE EL NUMERO DE VECINOS DE ORDEN K DE UN CONJUNTO DE VERTICES Y, COMO CASO PARTICULAR DE ESTE RESULTADO,