Sesión Matemática DiscretaAbout of the determinant K\H{o}nig-Egerv\'{a}ry graphs with a perfect matching
Gonzalo Molina
Universidad Nacional de San Luis, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
K\H{o}nig-Egerv\'{a}ry graphs were introduced in [1]. They are graphs where the covering number equals the matching number. There exists a rich literature on the topic; see, for example, [2] and [3]. Graphs with (a unique) perfect matching have been extensively studied in the literature, see for example [4] and [5]. Harary in 1962, [see [6] , and Sachs in 1964, see [7], introduced what are now known as Sachs subgraphs, which consist of subgraphs where all components are edges or cycles.
In this work, it is proved, v\'{\i}a the notion of posy intorduced by Deming in [1], that every K\H{o}nig-Egerv\'{a}ry graph with a perfect matching has a spanning bipartite graph with the same set of Sachs subgraphs, and therefore the same determinant.
Trabajo en conjunto con: Daniel A. Jaume (Universidad Nacional de San Luis).
Referencias
[1] Deming, R. W. (1979). Independence numbers of graphs-an extension of the k ̈onig-egerv ́ary theorem. Discrete Mathematics, 27(1):23–33.
[2] Levit, V. E. and Mandrescu, E. (2011). A characterization of K ̈onig– Egerv ́ary graphs using a common property of all maximum matchings. Electronic Notes in Discrete Mathematics, 38:565–570.
[3] Cardoso, D. M., Robbiano, M., and Rojo, O. (2017). Combinatorial and spectral properties of K ̈onig–Egerv ́ary graphs. Discrete Applied Mathe- matics, 217:446–454.
[4] Simion, R. and Cao, D. S. (1989). Solution to a problem of C D Godsil regarding bipartite graphs with unique perfect matching. Combinatorica, 9:85–89.
[5] Wang, X., Shang, W., and Yuan, J. (2015). On graphs with a unique perfect matching. Graphs and Combinatorics, 31:1765–1777.
[6] Harary, F. (1962). The determinant of the adjacency matrix of a graph. SIAM Review, 4(3):202–210.
[7] Sachs, H. (1964). Beziehungen zwischen den in einem graphen enthaltenen kreisen und seinem charakteristischen polynom. Publicationes Math- ematicae Debrecen, 11(1-4):119–134.