Nuevos resultados sobre el emparejamiento de grafos a partir del crecimiento que conserva el grado
Autores: Erds, Péter L.; Kharel, Shubha R.; Mezei, Tamás Róbert; Toroczkai, Zoltán
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Nuevos resultados sobre el emparejamiento de grafos a partir del crecimiento que conserva el grado
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Introducido
Modelo
Emparejamientos
Vértices
Grados
Secuencia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 28
Citaciones: Sin citaciones
El modelo recientemente introducido en el estudio de S. R. Kharel et al. [Crecimiento de redes que conservan grados, , 100-106] utiliza emparejamientos para insertar nuevos vértices de grados prescritos en el grafo actual de una secuencia de grafos en constante crecimiento. El proceso depende tanto del tamaño del emparejamiento más grande disponible, que es el enfoque de este artículo, como de la elección real del emparejamiento. Aquí, primero mostramos que la pregunta de si una secuencia de grados gráficos, extendida con un nuevo grado , sigue siendo gráfica es equivalente a la existencia de una realización de la secuencia de grados original con un emparejamiento de tamaño . En segundo lugar, presentamos cotas inferiores para el tamaño de los emparejamientos máximos en cualquier realización de la secuencia de grados. Luego estudiamos las cotas sobre el tamaño de los emparejamientos máximos en algunas realizaciones de la secuencia, conocido como el número de emparejamiento potencial. También estimamos el tamaño mínimo tanto de los emparejamientos máximos como de los emparejamientos máximos, según lo determinado por la secuencia de grados, independientemente de las realizaciones gráficas. A lo largo de esta línea respondemos a una pregunta planteada por T. Biedl et al.: Límites ajustados en emparejamientos máximos y máximos. , , 7-15.
Descripción
El modelo recientemente introducido en el estudio de S. R. Kharel et al. [Crecimiento de redes que conservan grados, , 100-106] utiliza emparejamientos para insertar nuevos vértices de grados prescritos en el grafo actual de una secuencia de grafos en constante crecimiento. El proceso depende tanto del tamaño del emparejamiento más grande disponible, que es el enfoque de este artículo, como de la elección real del emparejamiento. Aquí, primero mostramos que la pregunta de si una secuencia de grados gráficos, extendida con un nuevo grado , sigue siendo gráfica es equivalente a la existencia de una realización de la secuencia de grados original con un emparejamiento de tamaño . En segundo lugar, presentamos cotas inferiores para el tamaño de los emparejamientos máximos en cualquier realización de la secuencia de grados. Luego estudiamos las cotas sobre el tamaño de los emparejamientos máximos en algunas realizaciones de la secuencia, conocido como el número de emparejamiento potencial. También estimamos el tamaño mínimo tanto de los emparejamientos máximos como de los emparejamientos máximos, según lo determinado por la secuencia de grados, independientemente de las realizaciones gráficas. A lo largo de esta línea respondemos a una pregunta planteada por T. Biedl et al.: Límites ajustados en emparejamientos máximos y máximos. , , 7-15.