Matching Preclusion of (n,k)-Star Graphs

$$S_{n,1}$$
Consider $G=S_{n,1}$ ($n \geq 4$). Let $F=F_V ∪ F_E$ be any optimal strong matching preclusion set of vertices of and edges respectively. Now, $G-F_V≅K_{n-|F_V|}$ since itself $G≅K_n$, so it suffices to classify optimal matching preclusion of $K_{n-|F_V|}$ generally. By X, for any even number $r$, $\text{mp}(K_r)=r-1$ and all optimal solutions are trivial except when $r=4$ and there is the particular nontrivial preclusion formed by removing the edge set of a three-cycle. When $r$ is odd, we can observe the $r$ edge-distinct almost perfect matchings on $K_r$ formed by choosing a vertex, projecting a diameter from it, and pairing up points across the diameter. In such a situation we have proven $\text{mp}(K_r) ≥ r$. Thus $\text{smp}(G)=n-1$ and optimal solutions occur with trivial deletions and the deletions of $n-4$ vertices together with the edge set of a three-cycle.

$$S_{n,2}$$
Consider $G=S_{n,2}$ ($n \geq 9$). For each $i=1,...,n$, let $H_i ≅ K_{n-1}$ be the region of $G$ whose nodes are those with $i$ in the last position, and let $F_i=H_i∩F$. We shall call $H_i$ a component of $G$, and to prevent confusion there will be no mention of the traditionally established meaning of this term. Edges between components will be referred to as cross edges; note there is exactly one cross edge incident to any given vertex. Without loss of generality assume $|F_1| \geq |F_i|$ for all $i$. We tackle the problem based on the size of $F_1$. But first, a lemma which we shall use later:

Lemma 1: $S_{n,2}$ and $S_{n,2}-H_i$ for any component $H_i$ are "weakly" Hamiltonian connected for up to and including $n-7$ faults, that is, there remains a Hamilton path between any two vertices in distinct components. Proof: The latter graph shall prove to be more restrictive, so we focus our attention there. Note that by Y, each $K_{n-1}$ component may sustain $(n-1)-4$ faults and remain Hamiltonian connected. As well, after faulting, contracting every component down to a single point yields a $K_{n-1}$ graph with at most $n-6$ faults, so that it too is Hamiltonian connected, sustaining up two $2$ more faults. Now, on the original faulted graph let $a,b$ be vertices in distinct components. Pick a Hamilton path connecting the components of $a$ and $b$ after faulting the component contraction on up to two edges corresponding to cross edges from $a$ and $b$. Use this path to construct a Hamilton path between $a$ and $b$, traveling through each component and using Hamiltonian connectivity in each to start and end at the appropriate vertices for cross edging while hitting every vertex along the way.$~\square$

$|F_1|=n-1$

We perform casework on the number of vertices deleted.

Case 1: If $|F_V|=n-1$, the rest of the graph is Hamiltonian. Therefore, there exists either a perfect matching or almost perfect matching.

Case 2: If $0 < |F_V| < n-1$ then $|F_V|≠n-2,n-3$ (as otherwise $|F_E|≤0,1$ respectively and $|F_E|+|F_V| < n-1$). Now, we claim there are at most three isolated vertices; within $H_1-F_1$ let $s$ denote the number of isolated vertices, $r$ the remaining vertices, and $d$ the deleted vertices. Note that $|F_E| ≥ {s \choose 2} + rs$ to account for isolated-isolated edges and isolated-remaining edges respectively, and $|F_V| ≥ d$ to account for deleted vertices, hence ${s \choose 2} + rs + d ≤ n-1$. However, $rs ≥ r$ and ${s \choose 2} > s$ assuming $s > 3$, implying $d+{s \choose 2} + rs > d + s + r = |H_1| = n-1$, a contradiction unless $s≤3$. As well, $s≠2$ since the one vertex's isolation requires $n-2$ object deletions, necessitating $r=1$, but this would mean the "remaining" vertex is itself isolated. This also shows $s=3$ implies $H_1-F_1$ is merely three isolated nodes.

Now, assume $s=3$; let $x,y,z$ be the unique vertices left in $H_1$. Then $x,y,z$ have sole cross neighbors $a,b,c$ respectively distinct components of $G$. Evidently $G-H_1-a-b-c$ still contains a Hamilton path since none of the cross edges between the remaining $K_{n-2}$ and $K_{n-1}$ components are faulted by removing $a,b,c$ and each component remains Hamiltonian connected. Thus use this path and the edges $(x,a),(y,b),(z,c)$ to obtain a desired matching.

Assume $s=1$; undelete a vertex $t$ (and along with it its neighboring edges). Now in $H_1-(F-t)$ there are no isolated vertices and only the previously isolated vertex (call it $v$) has degree one, so by our analysis of $S_{n,1}$ we may observe a perfect or almost perfect matching $M$ of $H_1-(F-t)$. If $M$ is perfect, necessarily $v$ is matched with $t$; let $(v,r)$ be a cross edge. Now $G-H_1-r$ has a Hamilton path as discussed above, so from all this obtain a desired matching on $G$ after redeleting $t$. If $M$ is almost perfect, perform the same trick as above while also considering the cross edge of the unmatched vertex.

Assume $s=0$; the same argument as above holds when we undelete a vertex, consider the induced maximal submatching, eject up to two cross edges, and use a Hamilton path on the rest.

$|F_1|=n-2$

Case 1: If $H_1-F_1$ contains a perfect matching $M$ then a Hamilton path can be applied to the rest (there will be but one fault in $G-H_1$, so e.g. start in the faulted or a faulted-cross-edge-incident component and continue using the Hamiltonian connectivity of the components), and if $M$ is almost perfect, the result is routine; if necessary choose a different unmatched vertex to ensure it retains a cross edge neighbor $r$ (possible if $F$ is nontrivial), match it with this neighbor, and find a Hamilton path on the rest.

Case 2: If there is not a perfect or almost perfect matching, then there are two possibilities: a trivial deletion, or the deletion of $n-5$ vertices and the edge set of a three-cycle. In the event of a trivial deletion, we may still obtain a matching missing only the isolated $v$ and a remaining vertex $s$, since the remaining vertices form a complete subgraph. If $F$ is nontrivial we can if necessary rechoose $s$ so that $s,v$ have cross neighbors $q,r$ respectively. In the event of the second possibility let $s$ and $v$ be two degree-one vertices with accessible cross neighbors $q,r$ (and then match the other two vertices in $H_1-F_1$). In both events finish the desired matching by constructing a Hamilton path on the rest, which is possible as all the other components remain Hamiltonian connected (see $|F_1|=n-4$ for an examination of a more difficult construction).

$|F_1|=n-3$

We have a perfect or almost perfect matching in $H_1-F_1$.
Case 1: If there's a perfect matching, the rest of the graph contains a Hamilton path, as every other component is still Hamiltonian connected, so use this to construct a desired matching.

Case 2: If there's an almost perfect matching, then let $m$ be the missed vertex. Note that $H_1-F_1$ does not isolate any vertices, and furthermore at most one vertex has degree one (observe otherwise degree-one vertices $u,v$; originally $d(u)+d(v)=2n-4$, so $n-3$ deletions must contribute to removing at least $2n-6=2(n-3)$ from their combined degree. Since faulting a vertex removes $2$ and faulting an edge distinct from $(u,v)$ removes only $1$, we either have the deletion of every vertex besides $u$ and $v$ [but now there isn't an almost perfect matching], or $H_1-F_1$ is $K_3$ missing an edge [if $u,v$ have faulted cross edges this is a trivial "fishtail" preclusion of $G$ which allows a maximal matching missing two vertices, and if not we may proceed with the main argument]). Hence we may find at least three almost perfect matchings on $H_1-F_1$ each missing distinct vertices, so we may assume $m$ has an unfaulted cross edge $(m,m')$. Now the argument is a simpler case of the one we shall handle for $|F_1|=n-4$ now, where we find a Hamilton path on the rest of $G-H_1-F'-m'$.

$|F_1|=n-4$

We have a perfect or almost perfect matching in $H_1-F_1$. Let $F'=F-F_1$.
Case 1: If there's a perfect matching, the rest of the graph contains a Hamilton path, as every other component is still Hamiltonian connected, so use this to construct a desired matching.

Case 2: If there's an almost perfect matching, then since $H_1$ contains a Hamilton cycle by Q necessarily of odd length ≥3, we may assume this matching misses $m$ which has an intact cross edge $(m,m')$ (unless it is the semitrivial disconnection of $H_1-F_1≅K_3$ from the rest of the graph); include the cross edge $(m,m')$, and observe that the remaining components $H_i≅K_{n-1}$ have at most $4$ faults each, so that by Y they remain Hamiltonian connected. As well, the component contraction of $G-H_1-F$ yields a $K_{n-1}$ with at most $3$ faults, so it retains a Hamilton path. Use these facts to construct a Hamilton path on $G-H_1-F'-m'$ and obtain a desired matching.

$|F_1|≤n-5$

The component contraction of $G-F'$ contains a perfect or almost perfect matching as it is itself a $K_n$ ($n > 4$) with at most $n-1$ edge faults and no isolated vertices unless all $n-1$ cross edges of a component are removed and $F$ is trivial, and at most one vertex of degree one since there are not enough faults otherwise. Add one edge back in possibly to leave every vertex with at least two unfaulted edges to apply Z to find (1) there is a Hamilton path on this component contraction after we re-remove the edge. As well, (2) each $H_i≅K_{n-1}$ component remains Hamiltonian connected as mentioned above. Use these two facts to construct a Hamilton path on $G-F$ and obtain a desired matching.

$$S_{n,3}$$

Consider $G=S_{n,3}$ ($n \geq 11$). For each $i=1,...,n$, let $H_i ≅ S_{n-1,2}$ be the region of $G$ whose nodes are those with $i$ in the last position, and let $F_i=H_i∩F$. We shall call $H_i$ an outer component of $G$, and we shall refer to individual components of $H_i$ as inner components of $G$. Similarly, we shall use the terms inner and outer cross edges; note each point of $G$ lies in a component in which it projects exactly one inner cross edge, and outside of which it projects one outer cross edge. We shall handle cases based on the size of $F_1$. But first, a lemma:

Lemma 2: $S_{n,3}-H_i$ has a Hamilton path for up to and including $n-8$ faults. Proof: Note that by the first lemma each component remains weakly Hamilton connected, and also that the (outer) component contraction on the whole faulted graph yields a $K_{n-1}$ with no faults (there are $n-2$ outer cross edges between any two outer components), so it retains a Hamilton path. Use these facts to construct a Hamilton path by starting in a given outer component, selecting a point in a distinct inner component to which to run a Hamilton path in accordance with the Hamilton path on the outer component contraction (this is possible for each component as at most $n-7$ of the $n-2$ cross edges between components will be unavailable; $n-8$ from faulting and $1$ from requiring it be from a distinct inner component), and continuing in this fashion throughout each outer component.$~\square$

$|F_1|=n-1$

Note $F$ must contain at least two vertices, otherwise the outer cross edges form a desired matching. Thus, let $a,b∈F$ be vertices and consider the perfect or almost perfect matching on $H_1-(F_1-a-b)$; we may assume $(a,b)$ is not part of this matching otherwise $G-F$ has a desired matching, and similarly neither $a$ nor $b$ are missed by this matching, so let $(a,c)$ and $(b,d)$ be edges in the matching. Consider the outer cross edges $e,f$ of $c,d$ respectively; we may find a perfect or almost perfect matching on $G-H_1-e-f$ by lemma 2 since $n≥10$, and perfectly match the rest.

$|F_1|=n-2$

Case 1: We have a perfect or almost perfect matching on $H_1-F_1$. With a perfect matching, we can perfectly match every other unfaulted outer component and maximally match the remaining one to obtain a desired matching on $G-F$. If there's an almost perfect matching missing $m$, then if $F$ is not trivial we may possibly rechoose $m$ so that it has an available outer cross edge $m''$. Add the matching on $H_1-F_1-m''$ plus $(m,m'')$ to a Hamilton path on the rest by lemma 2 to obtain a desired matching on $G-F$.

Case 2: We don't have a perfect or almost perfect matching. By our work on $S_{n,2}$, we may break this down into three subcases based on the semitrivial preclusions.

Trivial: The vertex $t$ is isolated from the odd number of vertices left, a maximal matching missing $t$ and $v$. If $F$ is nontrivial we may assume an outer cross edge $(t,t'')$ and possibly rechoose $v$ to assume its own outer cross edge $(v,v'')$. By the lemma finish a desired matching on $G-F$ with a Hamilton path on the rest since $n≥11$. Component Disconnection: Perform the same trick on the missed vertices inside and outside the disconnected component. Fishtail: Choose a matching missing one of the "fins" that has an unfaulted outer cross edge, and now perform the same trick again.

$|F_1|=n-3$

If $H_1-F_1$ has a perfect matching, by lemma 2 we may use a path to find a desirable matching on $G-F$ since $n≥10$. If there is an almost perfect matching, then we cannot have two vertices of degree one in $H_1-F_1$, since each has $n-2$ neighbors originally, and by considering (inner) cross edges they do not have the same set of neighbors. Since there are no isolated vertices, this implies (as in the case of $|F_1|=n-3$ for $S_{n,2}$) three distinct matchings missing distinct vertices, so that we may assume an almost perfect matching missing $m$ with an intact outer cross edge $(m,m'')$. As usual apply lemma 2 to finish a matching with a path on the rest.

$|F_1|≤n-4$

We turn our focus momentarily to prove a fact about $S_{n,2}$, that is, that it contains a Hamiltonian cycle for up to and including $n-3$ deletions from $K$ (for $n≥6$). We break it down by case on the size of $K_1 := K∩H_1$. If $|K_1|=n-3$, then $H_1-F_1$ contains a Hamiltonian path, so use its endpoints and the Hamiltonian connectivity of the other components to complete the cycle. If $|K_1|=n-4$, then $H_1-F_1$ contains a Hamiltonian cycle by Q (this result isn't making any sense!); use it to find a Hamiltonian path as before on $H_1$ with endpoints of unfaulted cross edges, and again use Hamiltonian connectivity of the other components to complete the cycle. If $|K_1|≤n-5$ then every component is Hamiltonian connected, and the component contraction of $S_{n,2}-K$ yields a $K_n$ with at most $n-3$ edge faults, and so contains a Hamiltonian cycle; use these to construct the cycle.

Now, we return to $G-F$. Note that each faulted outer component $H_i-F_i$ now contains a Hamiltonian cycle by the above. Each pair of outer components share $n-2$ outer cross edges, so we divide into two cases based on whether all $n-2$ between a pair have been faulted.

Case 1: Every pair of faulted outer components retains an outer cross edge between them. Then pair up odd-length Hamiltonian cycles within each outer component, leaving one out if necessary. Using an outer cross edge between each pair, we may perfectly match each pair of odd-length Hamiltonian cycle components and all the even-length ones individually, giving a desired matching on $G-F$.

Case 2: The outer cross edges between $H_i$ and $H_j$ have all been faulted, and necessarily every other pair retains a common cross edge. The process is as easy as above unless $H_i-F_i$ and $H_j-F_j$ are the unique odd-length Hamiltonian cycles. However, in this case $n-2$ of the $n-1$ deletions are within $H_i$, $H_j$ or the outer cross edges between them; this implies there is at most one other component with a fault. Choose an unfaulted component $H_k$, send two outer cross edges into it from $H_i$ and $H_j$ (preferably into distinct inner components), and use Hamiltonian connectivity on $H_k$ to take care of $H_i$, $H_j$, and $H_k$ and obtain a desired matching on $G-F$.

$$S_{n,k}$$

We shall prove by induction on $k$ that $S_{n,k}$ is super strongly matched when $n-8≥k≥3$. We have established the base case when $k=3$. Now, observe general $G=S_{n,k}$. We carry familiar terminology into this case.

$|F_1|=n-1$

Case 1: $H_1-F_1$ retains a perfect or almost perfect matching. In either case we may perfectly match the rest as each component is even, to obtain a desired matching on $G-F$.

Case 2: $H_1-F_1$ does not contain a perfect or almost perfect matching. Similar as to $S_{n,3}$ when $|F_1|=n-1$ we may undelete two vertices $a,b$ to find they take part in a matching with $c,d$ respectively, which have cross edge neighbors $e,f$ respectively. If $e,f$ are in the same outer component then perfectly match it, the rest, and the maximal matching in $H_1-(F_1-c-d)$ to obtain a desired matching, and if they are in different outer components, send an outer cross edge between the components to the same effect.

$|F_1|=n-2$

Case 1: $H_1-F_1$ has a perfect or almost perfect matching. The argument is verbally identical to the parallel case in $S_{n,3}$, though we argue the end by considering outer cross edges as above rather than by Hamilton path.

Case 2: We don't have a perfect or almost perfect matching. By induction this must only be a trivial deletion isolating $m$ and resulting in a matching missing $m$ and $t$. If $F$ itself is not trivial, we may use the outer cross edge $(m,m'')$ and possibly rechoose $t$ to also keep its outer cross edge $(t,t'')$. Add these to the matching and if necessary cross edge between two components to obtain a desired matching on $G-F$.

$|F_1|=n-3$

$H_1-F_1$ contains a perfect or almost perfect matching. It is familiar enough to clean up in the former case, and in the latter case it is simple enough to prove no two vertices in $H_1$ can have the same set of neighbors, hence $H_1-F_1$ leaves at most one vertex with degree one and we may use three missed-vertex-distinct almost perfect matchings to select one with a missed vertex having an unfaulted outer cross edge. The cleanup is again routine.

$|F_1|≤n-4$

When $n > 7$ and $k≥4$ we have at least $(n-2)(n-3)=n^2-5n+6 > n-1$ outer cross edges between any pair of components, so for each pair of faulted components with only an odd number of vertices, we may connect them by an outer cross edge and have few enough faults to perfectly match what remains within that pair. This gives rise to a desired matching on $G-F$ and finishes the inductive step.