Palabras clave
grafo simple conexo
rango mínimo semidefinido
δ-grafo
C-δ grafo
representación ortogonal
delta conjecture
simple connected graphs
minimum semidefinite rank
δ-graph
C-δ graphs
orthogonal representation
Cómo citar
Resumen
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.
Citas
AIM Minimum Rank-Special Graphs Work Group (Barioli, B.; Barrett, W.; Butler, S.; Cioaba, S.; Fallat, S.; Godsil, C.; Haemers, W.; Hogben, L.; Mikkelson, R.; Narayan, S.; Pryporova, O.; Sciriha, I.; Stevanovic, D.; Van Der Holst, H.; Van Der Meulen, K.; Wangsness, A.) (2008) “Zero forcing sets and the minimum rank of graphs", Linear Algebra and its Applications 428(7): 1628–1648.
Barioli, F.; Barrett, W.; Fallat, S.; Hall, H.; Hogbend, L.; van der Holst, H. (2012) “On the graph complement conjecture for minimum rank", Linear Algebra and its Applications 436(12): 4373–4391.
Barioli, F.; Barrett, W.; Fallat, S.; Hall, H.; Hogbend, L.; Shader, B.; van den Driessche, P.; van der Holst, H. (2010) “Zero forcing parameters and minimum rank problems", Linear Algebra and its Applications 433(2): 401–411.
Barioli, F.; Fallat, S.; Mitchell, L.; Narayan, S. (2011) “Minimum semidefinite rank of outerplanar graphs and the tree cover number", Electronic Journal of Linear Algebra 22(2): 10–21.
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 Certain Graphs Classes”, in: NSF-REU Report from Central Michigan University (Summer 2007).
Berman, A.; Friedland, S.; Hogben, L.; Rothblum, U.; Shader, B. (2008) "An upper bound for the minimum rank of a graph", Linear Algebra and its Applications 429(7): 1629–1638.
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 semidefinite rank of a simple graph", Linear and Multilinear Algebra 59(5): 483–506.
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, W. (2008) “On the minimum rank among positive semidefinite matrices with a given graph", SIAM Journal on Matrix Analysis and Applications 30(2): 731–740.
Brandstädt, A.; Spinrad, J.; Le, V. (1999) Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA.
Brualdi, R.; Leslie, H.; Shader, B. (2007) AIM workshop spectra of families of matrices described by graphs, digraphs, and sign patterns final report: mathematical results, en: http://www.aimath.org/pastworkshops/matrixspectrumrep.pdf
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 Department, Central Michigan University, Michigan.
Ekstrand, J.; Erickson, C.; Hall, H.; Hay, H.; Hogben, L.; Johnson, R.; Kingsley, N.; Osborne, S.; Peters, T.; Roat, J.; Ross, A.; Row, D.; Warnberg, N.; Young, M. (2013) “Positive semidefinite zero forcing”, Linear Algebra and its Applications 439(7): 1862-1874.
Fallat, S.M.; Hogben, L.(2007) “The minimum rank of symmetric matrices described by a graph: a survey", Linear Algebra and its Applications 426(2-3): 558–582.
Hackney, P.; Harris, B.; Lay, M.; Mitchell, L.H.; Narayan, S.K.; Pascoe, A. (2009) “Linearly independent vertices and minimum semidefinite rank", Linear Algebra and its Applications 431(8): 1105–1115.
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 428(7): 1685–1695.
Mitchell L.(2011) “On the graph complement conjecture for minimum semidefinite rank", Linear Algebra and its Applications 435(6): 1311– 1314.
Mitchell, L.H.; Narayan, S.K.; Zimmerc, A.M. (2010) “Lower bounds in minimum rank problems", Linear Algebra and its Applications 432(1): 430–440.
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.