Graphs constructed from sums of perfect matchings

Question

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})=\bigcup_{i=1}^k E(M_i)$ be the union of all the edges appearing in perfect matchings 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 extremal graph theory? I have in mind results in which the size of the collection $\mathcal{M}$ plays an analogous role to the number of edges in classical results in that field, like the Erdős–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 the question Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs), 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.

Answer 1

A graph constructed with a collection of perfect matchings is called a matching covered graph.

Answer 2

Deciding if a given graph (or type of graph) can be constructed this way would seem the more likely question. When it can, there is sometimes a name for a particular construction of this type. The circle method is one of several to construct a round robin tournament for $k+1$ players when $k$ is odd: A $k$ day tournament where each player plays one match each day and at the end all pairs have played. Consider the players as vertices of a complete graph $K_{k+1}$ and color the edges according to the day that pair plays their match. This decomposes the $\binom{k+1}2$ edges into $k$ perfect matchings.

Digression: There is much work on deciding if a graph $G$ is $k$-vertex colorable.
Maximum degree $\lt k$ is certainly a sufficient condition.
Here is a construction of such a graph: Start with $k$ disjoint vertex sets (some perhaps empty) and add some edges, but only between vertices in different sets. The result is certainly $k$-vertex-colorable and every such graph arises that way. But the construction does not have a name as far as I know.

Here are some more interesting properties for a regular graph. Consider a simple graph $G$ which is regular of degree $k.$ Then the vertex coloring number is at most $k+1$ and could be $2.$ The edge coloring number is at least $k.$ We might wonder if it has one or the other of these properties:

I) It can be vertex colored with $k+1$ colors so that each vertex has one neighbor of each color other than it's own.

II) It can be $k$-edge colored.

The complete graph $K_{k+1}$ somewhat trivially has property I.

It is less obvious that, for $k$ odd, $K_{k+1}$ has property II. One way of proving this is the circle method mentioned above.

Another interesting result is that, for $k$ odd, property I implies property II: Given the coloring of $G$, color the vertices of $K_{k+1}$ with the same colors and consider a $k$-edge coloring of that complete graph as just mentioned. Now color each edge of (the vertex colored) $G$ with the same color as the correspondingly colored edge of the complete graph.

To get back to your question, it is immediate that property I precisely says that $G$ can be constructed in this way:

• Consider $k+1$ disjoint vertex classes, each of the same size. Then choose $\binom{k+1}2$ matchings, one between each pair of classes.

While property II ($G$ is $k$-regular and $k$-edge colorable) precisely says that it arises from your construction:

• Take $k$ edge disjoint perfect matchings ($1$-factors) on some $2m$ points. (I'm assuming simple graphs and $k>0$.)

But I don't know that either construction has a name in general.

The construction can easily be used to create a $k$-regular bipartite graph. But it turns out the converse is true as well. A $k$-regular bipartite graph has a perfect matching and hence $k$ disjoint perfect matchings. So every regular bipartite graph has property II.