Characterization of saturated graphs related to pairs of disjoint matchings

We investigate the ratio of two parameters of a finite graph $G$, $\frac{\mu(G)}{\nu(G)}$, where $\nu(G)$ is the size of a maximum matching in $G$, and $\mu(G)$ is the size of the largest matching in a pair of disjoint matchings whose union is as large as possible. More formally,

To place the mentioned parameters $\lambda,\mu$ and the ratio $\frac{\mu}{\nu}$ in the context of what is commonly considered in graph theory, recall that for $k\in\mathbb{N}$, a proper edge-coloring of a graph $G$ with $k$ colors is exactly a partition of the edge-set into $k$ disjoint matchings. Thus, determining $\lambda$ is the $k=2$ case of the following well-known problem:

We note here that $\nu=\nu_{1}$ and $\lambda=\nu_{2}$, so the $k=1$ case of this problem is the maximum matching problem, while the $k=2$ case is what we are concerned with here. Before describing our result, we overview what is known about $k$-ECS concerning its computational complexity, numerical bounds, and structural aspects.

Throughout, we denote by $G=(V,E)$ a finite graph with vertex set $V$ and edge set $E$. A matching in $G$ is a set of edges such that no two are adjacent. In particular, we will consider the following specific types of matchings.

• •

  A maximum matching is a matching $M$ of maximum size, i.e., for all matchings $M^{\prime}$, $|M^{\prime}|\leq|M|$. We let $\boldsymbol{\nu(G)}$ denote the size of a maximum matching.

• •

  A perfect matching is a matching $M$ such that for every vertex $v$ in $G$, there exists an $e\in M$ such that $v$ is incident to $e$.

• •

  A near perfect matching is a matching $M$ such that for every vertex $v$ in $G$ except for one, there exists an $e\in M$ such that $v$ is incident to $e$.

In addition to sizes of maximum matchings, we will also pay special attention to the size of the union of two disjoint matchings whose union is of maximum size. More formally:

• •

  $\boldsymbol{\lambda(G)}:=\max\{|H|+|H^{\prime}|:(H,H^{\prime})\text{ are disjoint matchings in }G\}$;

• •

  $\boldsymbol{\Lambda(G)}$ is the set of pairs $(H,H^{\prime})$ of disjoint matchings satisfying $|H|+|H^{\prime}|=\lambda(G)$;

• •

  $\boldsymbol{\mu(G)}:=\max\{|H|:\exists H^{\prime}\text{ such that }(H,H^{\prime})\in\Lambda(G)\}$.

$\nu$, $\lambda$, and $\mu$ are the main concern of this paper. We present an example with the spanner graph to illustrate our key parameters. The left spanner of Fig. 2 has the unique maximum matching, $M$, highlighted. It has size 5, and so $\nu(G)=5$ for the spanner. The largest matching disjoint from $M$ has size 2, for combined size of 7. However, if we choose a separate set of disjoint matchings, we can achieve $\lambda(G)=8$. On the right of the same figure, our maximal disjoint matchings $H$ and $H^{\prime}$ are highlighted. They each have size $4$, so $\mu(G)=4$ for the spanner. Most graphs with $\frac{\mu(G)}{\nu(G)}<1$ share key structural properties with the spanner, as we will make clear in Section 5.

• •

  $\boldsymbol{\Lambda_{\mu}(G)}$ is the subset of $\Lambda(G)$ of pairs $(H,H^{\prime})$ with $|H|=\mu(G)$.

• •

  $\boldsymbol{\mu^{\prime}(G)}:=\lambda(G)-\mu(G)$.

• •

  By a chain in $G$, we mean a sequence $(v_{0},e_{1},v_{1},e_{2},\dots,e_{\ell},v_{\ell})$, $\ell\in\mathbb{N}$, where the $v_{i}$ are vertices and the $e_{j}$ are edges of $G$ such $e_{i}=(v_{i-1},v_{i})$ for all $i\leq\ell$; we also assume that our chains are simple, i.e. all edges are distinct. We refer to $\ell$ as the length of the chain and to $v_{0}$ and $v_{\ell}$ as its endpoints.

• •

  By an odd (resp. even) chain we mean that the length (i.e., the number of edges on it) is odd (resp. even).

• •

  By a path, we mean a simple path, i.e. a chain with distinct vertices, and by a cycle we mean a simple cycle, i.e. a chain whose endpoints are equal but all other vertices are distinct.

• •

  An edge $e_{i}$ on an odd path $v_{0}e_{1}v_{1}e_{2}\dots e_{k+1}v_{2k+1}$ is called even (resp. odd) if $i$ is even (resp. odd). Note that this would not change if the path was written in the reverse order.

• •

  If $A,B\subseteq E$, then an $A-B$ alternating chain is a chain such that edges of odd index are in $A\setminus B$ and edges of even index are in $B\setminus A$, or vice versa. Note that if $A$ and $B$ are both matchings, then the chain must be either a path or a cycle, or else some vertex will be incident to two edges of the same matching.

• •

  If $A\subset E$ is a subset of the edges of the graph $G$, then $\boldsymbol{A^{c}}$:= $E\setminus A$ is the complement in $E$ of $A$.

Now, we present a type of decomposition for graphs that highlights matching structure and gives an alternative way to compute the parameters $\nu(G)$, $\lambda(G)$, and $\mu(G)$. Several of the following lemmas will be used in the proof of our main theorems. Throughout this section, let $G:=(V,E)$ be a graph and $n:=|V|$.

• •

  A subgraph of $G$ is a graph $G^{\prime}:=(V^{\prime},E^{\prime})$ with $V^{\prime}\subseteq V$ and $E^{\prime}\subseteq E$. A subgraph $G^{\prime}:=(V^{\prime},E^{\prime})$ of $G$ is spanning if $V^{\prime}=V$.

• •

  A pec decomposition of $G$ is a spanning subgraph $G^{\prime}:=(V,E^{\prime})$, each of whose (connected) components is a path or an even cycle. (Isolated vertices are treated as even paths.)

• •

  If $A$ is a subset of $E$, then we use the notation $\boldsymbol{G_{A}}:=(V,A)$ to denote the spanning subgraph of $G$ with edge set $A$. In particular, we use this notation in the case that $A$ is the union of certain matchings.

For a pec decomposition $G^{\prime}$ of $G$, let

• •

  $\boldsymbol{p(G^{\prime})}$ (resp., $\boldsymbol{ep(G^{\prime})}$) denote the number of components of $G^{\prime}$ that are paths (resp., even paths);

• •

  $\boldsymbol{p(G)}:=\min\{p(G^{\prime}):\text{$G^{\prime}$ is a pec decomposition of }G\}$;

• •

  $\boldsymbol{ep(G)}:=\min\{ep(G^{\prime}):\text{$G^{\prime}$ is a pec decomposition of }G\}$.

These last three parameters describe structural properties of the graph that can be assessed with matchings and alternating paths. They are a direct parallel to our original $\nu,\mu$, and $\lambda$. For our first lemma, we show that $\nu(G)$ and $ep(G)$ are directly related.

We can find a similar correspondence between $\lambda(G)$ and $p(G)$ if we consider the pairs of disjoint matchings in $G$ instead of the maximum matchings.

Now, define

i.e. $ep^{*}(G)$ is the minimum number of even paths in a pec decomposition that minimizes the number of paths. If we now take $(H,H^{\prime})\in$ $\Lambda_{\mu}$ instead of $\Lambda$, we obtain a result for $\mu(G)$ and $ep^{*}(G)$.

These new $e,ep^{*},$ and $p$ parameters provide as much information as our original $\nu,\mu$, and $\lambda$. In fact, we can now restate theorems concerning the ratio $\frac{\mu(G)}{\nu(G)}$ in terms of our new pec parameters.

We present one more brief result for pec decompositions that is useful in studying size differences of disjoint matchings.

As we will demonstrate in the next section, these matchings capture the most important structural behavior of $\frac{\mu(G)}{\nu(G)}<1$ graphs. Throughout this section, let $M$, $H$, $H^{\prime}$ be maximally intersecting matchings. Here are a few basic facts about $M$-$H$ alternating chains. Define an end-edge of a path to be an edge in the path incident to one of the path’s terminal vertices.

We now present similar structural lemmas about maximal $H$-$H^{\prime}$ alternating paths.

We are now prepared to state and prove our main theorems. For $d\in\mathbb{N}$, we call a vertex in a graph a $d$-vertex if its degree is $d$, and we say that a graph has degree $d$ if the degree of each vertex is at most $d$. An edge incident to a leaf (a $1$-vertex) is called a leaf-edge.

A path in a graph whose end-vertices are leaves is called leaf-to-leaf. Call an edge $e$ on an odd path $p$ odd (resp. even) if it is in an odd (resp. even) position in both obvious orderings of the $p$ edges, i.e. the end edges of $p$ are both odd. Similarly, call a vertex $v$ on an even path $p$ odd (resp. even) if its edge-distance from either end-edge of $p$ is odd (resp. even).

Our main theorems, Theorem 19 and Theorem 20, establish that the core structural properties of graphs with $\frac{\mu(G)}{\nu(G)}<1$ are due to a graph’s skeleton structure.

The main theorems of this paper, Theorem 19 and Theorem 20, make the following characterization. A connected graph $G=(V,E)$ is a $k$-skeleton if and only iff $\nu(G)-\mu(G)=k$ and any $M,H,H^{\prime}$ satisfying conditions (a)–(d) cover all of $E$, i.e., $E=M\cup H\cup H^{\prime}$. This condition for an edge covering of $G$ is not arbitrary; the key structural properties in a graph that cause $\frac{\mu(G)}{\nu(G)}<1$ are included in the definition of skeleton, and there are very few ways that edges not in this choice of $(M,H,H^{\prime})$ can be added to a skeleton $G$ without forcing $\frac{\mu(G)}{\nu(G)}=1$. A brief discussion for these remaning unmatched edges appears in the last section.

We prove a proposition before proving our main theorems.

This unique perfect matching is used in our first main theorem. Our proof uses structural properties derived from the pec parameters of Section 3. For a pair $(H,H^{\prime})$ of disjoint matchings, call a vertex $v\in V$ $(H,H^{\prime})$-saturated (or just saturated if $(H,H^{\prime})$ is clear from the context) if $\deg_{G_{H\cup H^{\prime}}}(v)=\min\left\{2,\deg_{G}(v)\right\}$, where $G_{H\cup H^{\prime}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(V,H\cup H^{\prime})$.