Sesión Matemática DiscretaAbout unimodularity of barbells graphs
Cristian Panelo
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.
Graphs with a unique perfect matching have been extensively studied in the literature, see [1] and [2]. A graph $G$ is unimodular if $\left|\det(G)\right|=1$. In [3], the problem of characterizing unimodular graphs is proposed, and unicyclic unimodular graphs are characterized. A K\H{o}nig-Egerv\'{a}ry graph is a graph such that its vertex covering number equals its matching number. K\H{o}nig-Egerv\'{a}ry graphs were independently introduced in 1979 by Deming [4] and Sterboul [5]. An even subdivision of a graph $G$ is either the graph $G$ itself or any of the graphs that arise from $G$ by successive application of even subdivisions. A barbell is the graph formed by two disjoint \(K_{3}\) linked by an edge. We also refer as a barbell graph to any even subdivision of it. In [6], the notion of a barbell part, $\text{B}(G)$, of a graph $G$ with a unique perfect matching was introduced. It was shown that every such graph $G$ can be decomposed into two disjoint subgraphs: $\text{KE}(G)$ (a K\H{o}nig-Egerv\'{a}ry graph) and $\text{B}(G)$ (the subgraph induced by all vertices in $M$-barbells of $G$). A graph $G$ is called a B-graph if $\text{B}(G)=G$.
In [6], it was proved that for all graphs with a unique perfect matching: $$\det(G) = \det(\text{B}(G)) \cdot \det(\text{KE}(G)).$$ Hence, in order to characterize when a graph is unimodular, it is necessary to characterize when K\H{o}nig-Egerv\'{a}ry graphs and B-graphs are unimodular. This work characterizes a large unimodular subfamily of B-graphs.
Trabajo en conjunto con: Daniel A Jaume (Universidad Nacional de San Luis) y Diego G Martinez (Universidad Nacional de San Luis).
Referencias
[1] R Simion and D S Cao. Solution to a problem of cd godsil regarding bipartite graphs with unique perfect matching. Combinatorica, 9:85–89, 1989
[2] S Panda and S Pati. On the inverse of a class of bipartite graphs with unique perfect matchings. The Electronic Journal of Linear Algebra, 29:89–101, 2015.
[3] S Akbari and S J Kirkland. On unimodular graphs. Linear Algebra and its Applications, 421(1):3–15, 2007
[4] R W Deming. Independence numbers of graphs - an extension of the K\H{o}nig-Egerv\'{a}ry Theorem. Discrete Mathematics, 27(1):23–33, 1979.
[5] F Sterboul. A characterization of the graphs in which the transversal number equals the matching number. 1979.
[6] D A Jaume, C Panelo, and D G Martinez, Determinantal decomposition of graphs with unique perfect matching, submitted