Skip to main content
1 of 2

Reference request - graphs constructed from sums of perfect matchings

Consider the following natural procedure for constructing graphs from perfect matchings in graphs with even number of vertices.

Let $V$ be the set of vertices of cardinality $|V|=2n$ and let $\mathcal{M}=\lbrace{M_1,M_2,\ldots, M_k\rbrace}$ be a collection of perfect matchings of vertices in $V$ (understoood as graphs whose edges form a partition of $V$ into two element disjoint subsets). Let $E(\mathcal{M})=\cup_{i=1}^k E(M_i)$ be the of all the edges appearing in perfect mathings in $\mathcal{M}$. We now define a graph whose edge set is precisely $E(\mathcal{M})$ i.e. $G(\mathcal{M})=(V,E(\mathcal{M}))$.

Question: Does this construction have a name in the literature? If so, were the graphs constructed in this way studied from the perspective of extreme graph theory. I have in mind results in which the size of the collection $\mathcal{M}$ plays an analogous role as number of edges in classical results in that field, like Erdos-Stone or Kővári–Sós–Turán theorems.

Remark: Although it is possible to lower bound the number of edges in a graph based on the number of prefect matchings (see for example discussion in this question), I suspect that stronger results concerning forbidden subgraphs could be derived for the class of graphs constructed in this way. Specifically, classical results on forbidden subgraphs assumed that subgraphs whose existence we want to exclude have fixed size, while the number of vertices of the ambient graph increases. I hope that this limitation can be lifted for the class of graphs considered here.