De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
"K-core" vuelve a dirigir aquí. El núcleo de un gráfico es un concepto diferente.
Un gráfico de 2 degeneraciones: cada vértice tiene como máximo dos vecinos a su izquierda, por lo que el vértice más a la derecha de cualquier subgráfico tiene un grado como máximo dos. Su 2-core, el subgrafo que queda después de borrar repetidamente vértices de grado menor que dos, está sombreado.

En teoría de grafos , un grafo k -degenerado es un grafo no dirigido en el que cada subgrafo tiene un vértice de grado como máximo k : es decir, algún vértice en el subgrafo toca k o menos de los bordes del subgrafo. La degeneración de un gráfico es el valor más pequeño de k para el que es k -degenerado. La degeneración de una gráfica es una medida de cuán escasa es y está dentro de un factor constante de otras medidas de escasez, como la arboricidad de una gráfica.

La degeneración también se conoce como el número k -core , [1] ancho , [2] y enlace , [3] y es esencialmente el mismo que el número de coloración [4] o el número de Szekeres-Wilf (llamado así por Szekeres y Wilf  ( 1968) )). Los gráficos k -degenerados también se han llamado gráficos k -inductivos . [5] La degeneración de un gráfico puede calcularse en tiempo lineal mediante un algoritmo que elimina repetidamente los vértices de grado mínimo. [6] ElLos componentes conectados que quedan después de eliminar todos los vértices de grado menor que k se denominan k núcleos del gráfico y la degeneración de un gráfico es el valor más grande k tal que tiene un k núcleo.

Ejemplos [ editar ]

Cada bosque finito tiene un vértice aislado (incidente a ningún borde) o un vértice de hoja (incidente exactamente a un borde); por lo tanto, los árboles y los bosques son gráficos degenerados en 1. Cada gráfico 1 degenerado es un bosque.

Cada grafo plano finito tiene un vértice de grado cinco o menos; por lo tanto, cada gráfico plano tiene 5 degeneraciones y la degeneración de cualquier gráfico plano es como máximo cinco. De manera similar, cada grafo del plano exterior tiene una degeneración como máximo dos, [7] y las redes apolíneas tienen una degeneración tres.

El modelo de Barabási-Albert para generar redes aleatorias sin escala [8] está parametrizado por un número m tal que cada vértice que se agrega al gráfico tiene m vértices previamente agregados. De ello se deduce que cualquier subgrafo de una red formada de esta manera tiene un vértice de grado como máximo m (el último vértice del subgrafo que se ha agregado al gráfico) y las redes Barabási-Albert son automáticamente m -degeneradas.

Cada gráfico k -regular tiene una degeneración exactamente  k . Más fuertemente, la degeneración de un gráfico es igual a su grado máximo de vértice si y solo si al menos uno de los componentes conectados del gráfico es regular de grado máximo. Para todos los demás gráficos, la degeneración es estrictamente menor que el grado máximo. [9]

Definiciones y equivalencias [ editar ]

El número de coloración de un gráfico G fue definido por Erdős y Hajnal (1966) como el menor κ para el que existe un orden de los vértices de G en el que cada vértice tiene menos de κ vecinos que están antes en el orden. Debe distinguirse del número cromático de G , el número mínimo de colores necesarios para colorear los vértices de modo que no haya dos vértices adyacentes del mismo color; el orden que determina el número de coloración proporciona un orden para colorear los vértices de G con el número de coloración, pero en general el número cromático puede ser menor.

La degeneración de un gráfico G fue definido por Lick y White (1970) como el mínimo k tal que cada subgrafo inducido de G contiene un vértice con k vecinos o menos. La definición sería la misma si se permiten subgrafos arbitrarios en lugar de subgrafos inducidos, ya que un subgrafo no inducido solo puede tener grados de vértice que sean menores o iguales a los grados de vértice en el subgrafo inducido por el mismo conjunto de vértices.

Los dos conceptos de número para colorear y degeneración son equivalentes: en cualquier gráfico finito, la degeneración es solo uno menos que el número para colorear. [10] En efecto, si un gráfico tiene un ordenamiento con el colorante número κ entonces en cada subgrafo H el vértice que pertenece a H y es el último en el orden tiene como máximo κ - 1 vecinos en H . En la otra dirección, si G es k -degenerado, entonces se puede obtener un orden con el número de coloración k  + 1 encontrando repetidamente un vértice v con un máximo de k vecinos, quitando v del gráfico, ordenando los vértices restantes y sumando v hasta el final del pedido.

Una tercera formulación equivalente es que G es k -degenerado (o tiene un número de coloración como máximo k  + 1) si y solo si los bordes de G pueden orientarse para formar un gráfico acíclico dirigido con un grado superior a lo sumo k . [11] Tal orientación puede formarse orientando cada borde hacia el primero de sus dos extremos en un orden de números de colores. En la otra dirección, si se da una orientación con un grado superior a k , se puede obtener una ordenación con un número de coloración k  + 1 como una ordenación topológica del gráfico acíclico dirigido resultante.

k -Cores [ editar ]

Un k -core de un gráfico G es un subgráfico conectado máximo de G en el que todos los vértices tienen al menos un grado k . De manera equivalente, es uno de los componentes conectados del subgrafo de G formado al borrar repetidamente todos los vértices de grado menor que k . Si existe un k- core no vacío , entonces, claramente, G tiene degeneración al menos k , y la degeneración de G es el k más grande para el cual G tiene un k- core.

Un vértice tiene coreness si pertenece a un -core pero no a ningún -core.

El concepto de k -core se introdujo para estudiar la estructura de agrupamiento de las redes sociales [12] y para describir la evolución de los gráficos aleatorios . [13] También se ha aplicado en bioinformática , [14] visualización de redes , [15] estructura de Internet, [16] propagación de crisis económicas, [17] identificación de difusores influyentes, [18] estructura de la corteza cerebral [19] o resiliencia de redes en ecología . [20] Extensiones de kTambién se han desarrollado estructuras centrales en redes ponderadas. [21] Un estudio del tema, que cubre los conceptos principales, técnicas algorítmicas importantes, así como algunos dominios de aplicación, se puede encontrar en Malliaros et al. (2019) .

La percolación Bootstrap es un proceso aleatorio estudiado como modelo epidémico [22] y como modelo de tolerancia a fallos para la computación distribuida . [23] Consiste en seleccionar un subconjunto aleatorio de celdas activas de un enrejado u otro espacio, y luego considerar el k -core del subgráfico inducido de este subconjunto. [24] En la percolación de k-core o bootstrap en redes débilmente interconectadas, las interconexiones pueden considerarse como un campo externo en la transición. [25]

Algoritmos [ editar ]

Como describen Matula y Beck (1983) , es posible encontrar una ordenación de vértices de un gráfico finito G que optimiza el número de coloración de la ordenación, en tiempo lineal , mediante el uso de una cola de cubos para encontrar y eliminar repetidamente el vértice de menor grado. . La degeneración es entonces el grado más alto de cualquier vértice en el momento en que se elimina. Sea n el número de nodos en el gráfico.

Con más detalle, el algoritmo procede de la siguiente manera:

  • Inicializar una lista de salida L .
  • Calcular un número d v para cada vértice v en G , el número de vecinos de v que no están ya en L . Inicialmente, estos números son solo los grados de los vértices.
  • Inicialice una matriz D tal que D [ i ] contenga una lista de los vértices v que aún no están en L para los cuales d v  =  i .
  • Inicialice k en 0.
  • Repite n veces:
    • Escanee las celdas de la matriz D [0], D [1], ... hasta encontrar una i para la que D [ i ] no esté vacía.
    • Establecer k al máximo ( k , i )
    • Seleccione un vértice v de D [ i ]. Agregue v al principio de L y elimínelo de D [ i ].
    • Para cada vecino w de v que aún no esté en L , reste uno de d w y mueva w a la celda de D correspondiente al nuevo valor de d w .

Al final del algoritmo, k contiene la degeneración de G y L contiene una lista de vértices en un orden óptimo para el número de coloración. Los i- núcleos de G son los prefijos de L que consisten en los vértices agregados a L después de que k primero toma un valor mayor o igual que  i .

La inicialización de las variables L , d v , D y k se puede realizar fácilmente en tiempo lineal. Encontrar cada vértice v eliminado sucesivamente y ajustar las celdas de D que contienen los vecinos de v lleva un tiempo proporcional al valor de d v en ese paso; pero la suma de estos valores es el número de aristas del gráfico (cada arista contribuye al término en la suma del último de sus dos puntos finales) por lo que el tiempo total es lineal.

Relación con otros parámetros del gráfico [ editar ]

Si un gráfico G está orientado acíclicamente con fuera de k , entonces sus bordes pueden dividirse en k bosques eligiendo un bosque para cada borde saliente de cada nodo. Por tanto, la arboricidad de G es como mucho igual a su degeneración. En la otra dirección, un gráfico de n -vértices que se puede dividir en k bosques tiene como máximo k ( n  - 1) aristas y, por lo tanto, tiene un vértice de grado como máximo 2 k- 1 - por tanto, la degeneración es menos del doble de la arboricidad. También se puede calcular en tiempo polinomial una orientación de un gráfico que minimiza el grado de salida, pero no es necesario que sea acíclico. Los bordes de un gráfico con dicha orientación pueden dividirse de la misma manera en k pseudoforestales y, a la inversa, cualquier partición de los bordes de un gráfico en k pseudoforestales conduce a una orientación hacia fuera- k (eligiendo una orientación hacia fuera-1 para cada pseudoforesto) , por lo que el grado mínimo de tal orientación es la pseudoarboricidad , que nuevamente es como mucho igual a la degeneración. [26] El espesorestá también dentro de un factor constante de la arboricidad, y por tanto también de la degeneración. [27]

Un gráfico k -degenerado tiene un número cromático como máximo k  + 1; esto se demuestra mediante una simple inducción sobre el número de vértices que es exactamente como la demostración del teorema de los seis colores para gráficas planas. Dado que el número cromático es un límite superior en el orden de la camarilla máxima , la última invariante también es como mucho degeneración más uno. Al utilizar un algoritmo de coloración codicioso en un pedido con un número de coloración óptimo, se puede graficar el color de un gráfico degenerado k utilizando como máximo k  + 1 colores. [28]

Un grafo conectado con k vértices es un grafo que no se puede dividir en más de un componente eliminando menos de k vértices, o lo que es lo mismo, un grafo en el que cada par de vértices se puede conectar mediante k trayectos disjuntos de vértice k . Dado que estos caminos deben dejar los dos vértices del par a través de bordes disjuntos, un grafo conectado al vértice k debe tener una degeneración de al menos k . Los conceptos relacionados con k -cores pero basados ​​en la conectividad de vértices se han estudiado en la teoría de redes sociales bajo el nombre de cohesión estructural . [29]

Si un gráfico tiene un ancho de árbol o un ancho de ruta como máximo k , entonces es un subgráfico de un gráfico cordal que tiene un orden de eliminación perfecto en el que cada vértice tiene como máximo k vecinos anteriores. Por lo tanto, la degeneración es como máximo igual al ancho del árbol y como máximo igual al ancho de la ruta. Sin embargo, existen gráficos con degeneración limitada y ancho de árbol ilimitado, como los gráficos de cuadrícula . [30]

La conjetura Burr-Erdős refiere la degeneración de un gráfico de G al número Ramsey de G , la menos n tal que cualquier de dos borde de coloración de un n -vertex gráfico completo debe contener una copia monocromática de G . Específicamente, la conjetura es que para cualquier valor fijo de k , el número de Ramsey de k gráficos degenerados crece linealmente en el número de vértices de los gráficos. [31] La conjetura fue probada por Lee (2017) .

Gráficos infinitos [ editar ]

Aunque los conceptos de degeneración y número de coloración se consideran con frecuencia en el contexto de los gráficos finitos, la motivación original de Erdős y Hajnal (1966) fue la teoría de los gráficos infinitos. Para un grafo infinito G , se puede definir el número de coloración de forma análoga a la definición de grafos finitos, como el número cardinal más pequeño α tal que exista un buen orden de los vértices de G en el que cada vértice tiene menos de α vecinos que son antes en el pedido. La desigualdad entre los colores y los números cromáticos se mantiene también en este escenario infinito; Erdős y Hajnal (1966) afirman que, en el momento de la publicación de su artículo, ya era bien conocido.

La degeneración de subconjuntos aleatorios de celosías infinitas se ha estudiado con el nombre de percolación bootstrap .

Ver también [ editar ]

  • Teoría de grafos
  • Ciencia de la red
  • Teoría de la filtración
  • Estructura núcleo-periferia
  • Conjetura de Cereceda

Notas [ editar ]

  1. ^ Bader y Hogue (2003) .
  2. ^ Freuder (1982) .
  3. ^ Kirousis y Thilikos (1996) .
  4. ^ Erdős y Hajnal (1966) .
  5. ^ Irani (1994) .
  6. ^ Matula y Beck (1983) .
  7. ^ Lamer y blanco (1970) .
  8. ^ Barabási y Albert (1999) .
  9. ^ Jensen y Toft (2011) , p. 78 : "Es fácil ver que col ( G ) = Δ ( G ) + 1 si y solo si G tiene uncomponenteΔ ( G ) -regular". En la notación utilizada por Jensen y Toft, col ( G ) es la degeneración más uno, y Δ ( G ) es el grado máximo de vértice.
  10. ^ Matula (1968) ; Lick & White (1970) , Proposición 1, página 1084.
  11. ^ Chrobak y Eppstein (1991) .
  12. ^ Seidman (1983) .
  13. ^ Bollobás (1984) ; Zauczak (1991) ; Dorogovtsev, Goltsev y Mendes (2006) .
  14. ^ Bader y Hogue (2003) ; Altaf-Ul-Amin y col. (2003) ; Wuchty y Almaas (2005) .
  15. ^ Gaertler y Patrignani (2004) ; Álvarez-Hamelin y col. (2006) .
  16. ^ Carmi y col. (2007) .
  17. ^ Garas y col. (2010) .
  18. ^ Kitsak y col. (2010) .
  19. ^ Lahav y col. (2016) .
  20. ^ García-Algarra et al. (2017) .
  21. ^ Garas, Schweitzer y Havlin (2012) .
  22. ^ Balogh y col. (2012) .
  23. ^ Kirkpatrick y col. (2002) .
  24. ^ Adler (1991) .
  25. ^ Bruto, B; Sanhedrai, H; Shekhtman, L; Havlin, S (2020). "Las interconexiones entre redes actúan como un campo externo en las transiciones de percolación de primer orden". Revisión E física . 101 (2). arXiv : 1905.07009 . doi : 10.1103 / PhysRevE.101.022316 .
  26. ^ Chrobak y Eppstein (1991) ; Gabow y Westermann (1992) ; Venkateswaran (2004) ; Asahiro y col. (2006) ; Kowalik (2006) .
  27. ^ Dean, Hutchinson y Scheinerman (1991) .
  28. ^ Erdős y Hajnal (1966) ; Szekeres y Wilf (1968) .
  29. ^ Moody y White (2003) .
  30. ^ Robertson y Seymour (1984) .
  31. ^ Burr y Erdős (1975) .

Referencias [ editar ]

  • Adler, Joan (1991), "Bootstrap percolation", Physica A: Statistical Mechanics and its Applications , 171 (3): 453–470, Bibcode : 1991PhyA..171..453A , doi : 10.1016 / 0378-4371 (91) 90295-n CS1 maint: parámetro desalentado ( enlace )
  • Altaf-Ul-Amin, M .; Nishikata, K .; Koma, T .; Miyasato, T .; Shinbo, Y .; Arifuzzaman, M .; Wada, C .; Maeda, M .; Oshima, T. (2003), "Predicción de funciones de proteínas basadas en k- núcleos de redes de interacción proteína-proteína y secuencias de aminoácidos" (PDF) , Genome Informatics , 14 : 498–499, archivado desde el original (PDF) en 2007-09-27
  • Álvarez-Hamelin, José Ignacio; Dall'Asta, Luca; Barrat, Alain; Vespignani, Alessandro (2006), " Descomposición de k- núcleos: una herramienta para la visualización de redes a gran escala", en Weiss, Yair; Schölkopf, Bernhard; Platt, John (eds.), Advances in Neural Information Processing Systems 18: Actas de la Conferencia de 2005 , 18 , The MIT Press, p. 41, arXiv : cs / 0504107 , Bibcode : 2005cs ........ 4107A , ISBN 0262232537
  • Asahiro, Yuichi; Miyano, Eiji; Ono, Hirotaka; Zenmyo, Kouhei (2006), "Algoritmos de orientación de gráficos para minimizar el grado máximo", CATS '06: Proceedings of the 12th Computing: The Australasian Theory Symposium , Darlinghurst, Australia, Australia: Australian Computer Society, Inc., págs. 11– 20, ISBN 1-920682-33-3
  • Bader, Gary D .; Hogue, Christopher WV (2003), "Un método automatizado para encontrar complejos moleculares en grandes redes de interacción de proteínas", BMC Bioinformatics , 4 (1): 2, doi : 10.1186 / 1471-2105-4-2 , PMC  149346 , PMID  12525261
  • Balogh, József; Bollobás, Béla ; Duminil-Copin, Hugo; Morris, Robert (2012), "El umbral agudo para la percolación bootstrap en todas las dimensiones", Transactions of the American Mathematical Society , 364 (5): 2667-2701, arXiv : 1010.3326 , doi : 10.1090 / S0002-9947-2011-05552 -2 , MR  2888224
  • Barabási, Albert-László ; Albert, Réka (1999), "Emergence of scaling in random networks" (PDF) , Science , 286 (5439): 509–512, arXiv : cond-mat / 9910332 , Bibcode : 1999Sci ... 286..509B , doi : 10.1126 / science.286.5439.509 , PMID  10521342 , archivado desde el original (PDF) en 2006-11-11
  • Bollobás, Béla (1984), "La evolución de grafos dispersos", Teoría de grafos y combinatoria, Proc. Cambridge Combinatorial Conf. en honor a Paul Erdős , Academic Press, págs. 35–57
  • Burr, Stefan A .; Erdős, Paul (1975), "Sobre la magnitud de los números de Ramsey generalizados para gráficos", Conjuntos infinitos y finitos (Colloq., Keszthely, 1973; dedicado a P. Erdős en su 60 cumpleaños), vol. 1 (PDF) , Coloq. Matemáticas. Soc. János Bolyai, 10 , Amsterdam: North-Holland, págs. 214-240, MR  0371701
  • Carmi, S .; Havlin, S .; Kirkpatrick, S .; Shavitt, Y .; Shir, E. (2007), "A model of Internet topology using k-shell descomposition", Proceedings of the National Academy of Sciences , 104 (27): 11150-11154, arXiv : cs / 0607080 , Bibcode : 2007PNAS..10411150C , doi : 10.1073 / pnas.0701175104 , PMC  1896135 , PMID  17586683
  • Chrobak, Marek; Eppstein, David (1991), "Orientaciones planas con bajo grado de salida y compactación de matrices de adyacencia" (PDF) , Informática teórica , 86 (2): 243-266, doi : 10.1016 / 0304-3975 (91) 90020- 3
  • Dean, Alice M .; Hutchinson, Joan P .; Scheinerman, Edward R. (1991), "Sobre el grosor y la arboricidad de un gráfico", Journal of Combinatorial Theory , Serie B, 52 (1): 147-151, doi : 10.1016 / 0095-8956 (91) 90100-X , MR  1109429
  • Dorogovtsev, SN; Goltsev, AV; Mendes, JFF (2006), " k -core organization of complex networks", Physical Review Letters , 96 (4): 040601, arXiv : cond-mat / 0509102 , Bibcode : 2006PhRvL..96d0601D , doi : 10.1103 / PhysRevLett.96.040601 , PMID  16486798
  • Erdős, Paul ; Hajnal, András (1966), "Sobre el número cromático de gráficos y sistemas de conjuntos" (PDF) , Acta Mathematica Hungarica , 17 (1–2): 61–99, doi : 10.1007 / BF02020444 , MR  0193025
  • Freuder, Eugene C. (1982), "Una condición suficiente para una búsqueda sin retroceso", Journal of the ACM , 29 (1): 24–32, doi : 10.1145 / 322290.322292
  • Gabow, HN; Westermann, HH (1992), "Bosques, marcos y juegos: algoritmos para sumas y aplicaciones matroides", Algorithmica , 7 (1): 465–497, doi : 10.1007 / BF01758774
  • Gaertler, Marco; Patrignani, Maurizio (2004), "Análisis dinámico del gráfico del sistema autónomo", Proc. Segundo taller internacional sobre simulación y rendimiento entre dominios (IPS 2004) , págs. 13-24, CiteSeerX  10.1.1.81.6841
  • Garas, Antonios; Argyrakis, Panos; Rozenblat, Céline; Tomassini, Marco; Havlin, Shlomo (2010), "Worldwide spreading of economic crisis", New Journal of Physics , 12 (11): 113043, arXiv : 1008.3893 , Bibcode : 2010NJPh ... 12k3043G , doi : 10.1088 / 1367-2630 / 12/11 / 113043
  • Garas, Antonios; Schweitzer, Frank; Havlin, Shlomo (2012), "Método de descomposición Ak-shell para redes ponderadas", New Journal of Physics , 14 (8): 083030, arXiv : 1205.3720 , Bibcode : 2012NJPh ... 14h3030G , doi : 10.1088 / 1367-2630 / 14/8/083030
  • García-Algarra, Javier; Pastor, Juan Manuel; Iriondo, José María; Galeano, Javier (2017), "Ranking de especies críticas para preservar la funcionalidad de redes mutualistas utilizando la descomposición k -core", PeerJ , 5 : e3321, doi : 10.7717 / peerj.3321 , PMC  5438587 , PMID  28533969
  • Irani, Sandy (1994), "Colorear gráficos inductivos en línea", Algorithmica , 11 (1): 53–72, doi : 10.1007 / BF01294263
  • Jensen, Tommy R .; Toft, Bjarne (2011), Graph Coloring Problems , Wiley Series in Discrete Mathematics and Optimization, 39 , John Wiley & Sons, ISBN 9781118030745
  • Kirkpatrick, Scott; Wilcke, Winfried W .; Garner, Robert B .; Huels, Harald (2002), "Percolación en matrices de almacenamiento densas", Physica A: Mecánica estadística y sus aplicaciones , 314 (1–4): 220–229, Código bibliográfico : 2002PhyA..314..220K , doi : 10.1016 / S0378 -4371 (02) 01153-6 , MR  1961703
  • Kirousis, LM; Thilikos, DM (1996), "The linkage of a graph" (PDF) , SIAM Journal on Computing , 25 (3): 626–647, doi : 10.1137 / S0097539793255709 , archivado desde el original (PDF) en 2011-07- 21
  • Kitsak, Maksim; Gallos, Lazaros K .; Havlin, Shlomo; Liljeros, Fredrik; Muchnik, Lev; Stanley, H. Eugene; Makse, Hernán A. (29 de agosto de 2010), "Identificación de difusores influyentes en redes complejas", Nature Physics , 6 (11): 888–893, arXiv : 1001.5285 , Bibcode : 2010NatPh ... 6..888K , doi : 10.1038 / nphys1746
  • Kowalik, Łukasz (2006), "Esquema de aproximación para medidas de densidad de gráficos y orientación de grado más bajo", Actas del 17º Simposio Internacional sobre Algoritmos y Computación (ISAAC 2006) , Lecture Notes in Computer Science, Springer-Verlag, 4288 : 557–566 , doi : 10.1007 / 11940128_56 , ISBN 978-3-540-49694-6
  • Lahav, Nir; Ksherim, Baruc; Ben-Simon, Eti; Maron-Katz, Adi; Cohen, Reuven; Havlin, Shlomo (2016), " La descomposición de la capa K revela la organización cortical jerárquica del cerebro humano", New Journal of Physics , 18 (8): 083013, arXiv : 1803.03742 , Bibcode : 2016NJPh ... 18h3013L , doi : 10.1088 / 1367-2630 / 18/8/083013
  • Lee, Choongbum (2017), "Ramsey numbers of degenerate graphs", Annals of Mathematics , 185 (3): 791–829, arXiv : 1505.04773 , doi : 10.4007 / annals.2017.185.3.2
  • Lick, Don R .; White, Arthur T. (1970), " k -degenerate graphs", Canadian Journal of Mathematics , 22 : 1082–1096, doi : 10.4153 / CJM-1970-125-1
  • Łuczak, Tomasz (1991), "Tamaño y conectividad del núcleo k de un gráfico aleatorio" , Matemáticas discretas , 91 (1): 61–68, doi : 10.1016 / 0012-365X (91) 90162-U
  • Malliaros, Fragkiskos D .; Giatsidis, Christos; Papadopoulos, Apostolos N .; Vazirgiannis, Michalis (2019), "La descomposición central de las redes: teoría, algoritmos y aplicaciones" (PDF) , The VLDB Journal , doi : 10.1007 / s00778-019-00587-4
  • Matula, David W. (1968), "Un teorema mínimo-máximo para gráficos con aplicación a la coloración de gráficos", Reunión Nacional SIAM 1968, Revisión SIAM , 10 (4): 481–482, doi : 10.1137 / 1010115
  • Matula, David W .; Beck, LL (1983), "Smallest-last ordering and clustering and graph colour algoritmos", Journal of the ACM , 30 (3): 417–427, doi : 10.1145 / 2402.322385 , MR  0709826
  • Moody, James; White, Douglas R. (2003), "Cohesión estructural y arraigo: una concepción jerárquica de los grupos sociales" , American Sociological Review , 68 (1): 1–25, doi : 10.2307 / 3088904 , JSTOR  3088904
  • Robertson, Neil ; Seymour, Paul (1984), "Graph minors. III. Planar tree-width", Journal of Combinatorial Theory , Serie B, 36 (1): 49-64, doi : 10.1016 / 0095-8956 (84) 90013-3
  • Seidman, Stephen B. (1983), "Estructura de red y grado mínimo", Redes sociales , 5 (3): 269–287, doi : 10.1016 / 0378-8733 (83) 90028-X
  • Szekeres, George ; Wilf, Herbert S. (1968), "Una desigualdad para el número cromático de un gráfico", Journal of Combinatorial Theory , 4 : 1–3, doi : 10.1016 / S0021-9800 (68) 80081-X
  • Venkateswaran, V. (2004), "Minimizar el grado máximo", Matemáticas aplicadas discretas , 143 (1-3): 374-378, doi : 10.1016 / j.dam.2003.07.007
  • Wuchty, S .; Almaas, E. (2005), "Peeling the levast protein network", Proteomics , 5 (2): 444–449, doi : 10.1002 / pmic.200400962 , PMID  15627958