On delta-graphs and delta conjecture

• Autores: Pedro Díaz Navarro
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 25, Nº. 1, 2018, págs. 1-28
• Idioma: español
• DOI: 10.15517/rmta.v1i25.32228
• Títulos paralelos:
  • Sobre delta-grafos y la conjetura delta
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    In this paper we define two infinite families of graphs called C- graphs and -graphs and prove that -graphs satisfy delta conjecture. Also we see that C- graphs family contains the complements of -graphs. Finally we give a list of C- graphs and the relationship with the minimum semidefinite rank of these graphs.

  • English

    En este artículo definimos dos familias de grafos llamadas C- grafos y -grafos y se prueba que los -grafos satisfacen la conjetura delta. También vemos que la familia de los C- grafos contienen los complementos de los -grafos. Finalmente damos una lista de C- grafos y la relación con el rango mínimo semidefinido de estos grafos.

• Referencias bibliográficas
  • AIM Minimum Rank-Special Graphs Work Group (Barioli, B.; Barrett, W.; Butler, S.; Cioaba, S.; Fallat, S.; Godsil, C.; Haemers, W.; Hogben,...
  • Barioli, F.; Barrett, W.; Fallat, S.; Hall, H.; Hogbend, L.; van der Holst, H. (2012) “On the graph complement conjecture for minimum rank",...
  • Barioli, F.; Barrett, W.; Fallat, S.; Hall, H.; Hogbend, L.; Shader, B.; van den Driessche, P.; van der Holst, H. (2010) “Zero forcing parameters...
  • Barioli, F.; Fallat, S.; Mitchell, L.; Narayan, S. (2011) “Minimum semidefinite rank of outerplanar graphs and the tree cover number",...
  • Barrett, W.; van der Holst, H.; Loewy, R. (2004) “Graphs whose minimal rank is two", Electronic Journal of Linear Algebra 11(21): 258–280.
  • Beagley, J et al . (2007) “On the Minimum Semidefinite Rank of a Graph Using Vertex Sums, Graphs with msr(G) = |G| − 2, and the msrs of...
  • Berman, A.; Friedland, S.; Hogben, L.; Rothblum, U.; Shader, B. (2008) "An upper bound for the minimum rank of a graph", Linear Algebra...
  • Bollobás, B. (1998) Modern Graph Theory. Springer, Memphis, TN.
  • Bondy, A.; Murty, M. (2008) Graph Theory. Springer, San Francisco, CA.
  • Booth, M.; Hackney, P.; Harris, B.; Johnson, C.; Lay, M.; Lenker, T.; Mitchell, L.; Narayan, S.; Pascoe, A.; Sutton, B. (2011) “On the minimum...
  • Booth, M.; Hackney, P.; Harris, B.; Johnson, C.R.; Lay, M.; Mitchell, L.H.; Narayan, S.K.; Pascoe, A.; Steinmetz, K.; Sutton, B.D.; Wang,...
  • Brandstädt, A.; Spinrad, J.; Le, V. (1999) Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia,...
  • Brualdi, R.; Leslie, H.; Shader, B. (2007) AIM workshop spectra of families of matrices described by graphs, digraphs, and sign patterns final...
  • Chartrand, G.; Lesniak, L.; Zhang, P. (2010) Graphs & Digraphs. Taylor & Francis Group, Boca Raton, FL.
  • Diaz, P. (2014) On the Delta Conjecture and the Graph Complement Conjecture for Minimum Semidefinite Rank of a Graph. Ph.D Dissertation, Mathematics...
  • Ekstrand, J.; Erickson, C.; Hall, H.; Hay, H.; Hogben, L.; Johnson, R.; Kingsley, N.; Osborne, S.; Peters, T.; Roat, J.; Ross, A.; Row, D.;...
  • Fallat, S.M.; Hogben, L.(2007) “The minimum rank of symmetric matrices described by a graph: a survey", Linear Algebra and its Applications...
  • Hackney, P.; Harris, B.; Lay, M.; Mitchell, L.H.; Narayan, S.K.; Pascoe, A. (2009) “Linearly independent vertices and minimum semidefinite...
  • Holst, H. (2003) “Graphs whose positive semidefinite matrices have nullity at most two", Linear Algebra and its Applications 375: 1–11.
  • Horn, R,; Johnson, C. (1985) Matrix Analysis. Cambridge University Press, England.
  • Hogben, L. (2010) “Minimum rank problems", Linear Algebra and its Applications 432(8): 1961–1974.
  • Hogben, L. (2008) “Orthogonal representations, minimum rank, and graph complements", Linear Algebra and its Applications 428(11-12): 2560–2568.
  • Jianga, Y.; Mitchell, L.H.; Narayan, S.K.(2008) “Unitary matrix digraphs and minimum semidefinite rank", Linear Algebra and its Applications...
  • Mitchell L.(2011) “On the graph complement conjecture for minimum semidefinite rank", Linear Algebra and its Applications 435(6): 1311–...
  • Mitchell, L.H.; Narayan, S.K.; Zimmerc, A.M. (2010) “Lower bounds in minimum rank problems", Linear Algebra and its Applications 432(1):...
  • Narayan, S.; Sharawi, Y. (2014) "Bounds on minimum semidefinite rank of graphs", Linear and Multilinear Algebra 63(4): 774–787.
  • Nylen, P.M.(1996) “Minimum-rank matrices with prescribed graph", Linear Algebra and its Applications 248(15): 303–316.
  • Peters, T. (2012) “Positive semidefinite maximum nullity and zero forcing number", Electronic Journal of Linear Algebra 23(): 815–830.
  • Read,R.; Wilson, R. (1998) An Atlas of Graphs. Oxford University Press, Reino Unido.
  • Sharawi, Y. (2011) Minimum Semidefinite Rank of a Graph. Ph.D. Dissertation, Mathematics Department, Central Michigan University, Michigan.
  • West, D.B. (1996) Introduction to Graph Theory. Prentice Hall Inc, Estados Unidos.