# Conditional Matching Preclusion Number of Graphs

Authors: Yalan Li; Shumin Zhang; Chengfu Ye
Journal: Discrete Dynamics in Nature and Society
 (2023)

---

## Abstract

The conditional matching preclusion number of a graphG, denoted by mp1G, is the minimum number of edges whose deletion results in the graph with no isolated vertices that has neither perfect matching nor almost-perfect matching. In this paper, we first give some sharp upper and lower bounds of conditional matching preclusion number. Next, the graphs with large and small conditional matching preclusion numbers are characterized, respectively. In the end, we investigate some extremal problems on conditional matching preclusion number.


---

## Body

## 1. Introduction

All graphs are undirected, finite, and simple in this paper, refer to the book [1] for notation and terminology not described here. If a cycle contains every vertex of G exactly once, then we called it is a Hamiltonian cycle of G. A connected graph G is Hamiltonian if it exists a Hamiltonian cycle in G. Furthermore, if there exists a Hamiltonian path between any two vertices of G, then G is said Hamiltonian connected. Denoted EV1,V2 to be a edges set has one endpoint in V1 and another in V2. If an edge subset F satisfies G−F has neither perfect matching nor almost-perfect matching, then F is a matching preclusion set (MP for short) of G. Denoted mpG is the minimum number of edges of all MP set in G. The concept of matching preclusion was introduced in [2] and further studied in [3–18]. Some distributed algorithms require each vertex of the system to be matched by a neighbour vertex, and the matching preclusion number measures the robustness of a graph as a communications network topology. Meanwhile, matching preclusion number has a theoretical connection with conditional connectivity and “changing and unchanging of invariants.” In a network, a vertex with a special matching vertex after edge failure any time implies that tasks running on a fault vertex can be change into its matching vertex. Therefore, under this fault assumption, larger mp (G) signifies higher fault tolerance. However, in the network, the probability that the adjacent vertices of the same vertex fail at the same time is very small. So the question is if we delete edges, what are the basic obstructions to a perfect matching or an almost-perfect matching in the resulting graph if no isolated vertices are created. This motivates our next definition. If an edge subset F satisfies G−F has no isolated vertices and has neither perfect matching nor almost-perfect matching, then F is a conditional matching preclusion set (CMP for short). Denoted mp1G is the minimum number of all CMP set. At present, there have been some discussions about the conditional matching preclusion number of special graphs. We mainly want to discuss the conditional matching preclusion number of general graphs. We consider the following three problems in this paper.Problem 1. Compute the minimum integersn,k=minEG:G∈ψn,k, where ψn,k be the set of all graphs of order n with conditional matching preclusion number kProblem 2. Compute the minimum integerfn,k such that for every connected graph G of order n, if EG≥fn,k, then mp1G≥kProblem 3. Compute the maximum integergn,k such that for every connected graph G of order n, if EG≤gn,k, then mp1G≤kA basic obstruction to a perfect matching of even graph with no isolated vertex will be the existence of a pathu−w−v where the degrees of u and v are 1. Define veG=mindGu+dGv−2−yGu,v: u and v are distance 2 apart}, if u and v are adjacent, then yGu,v=1, and 0 otherwise.Proposition 1 (see [7]).
An even graphG with δG≥3, then mp1G≤veG.The basic obstruction to an almost-perfect matching of odd graph with no isolated vertex will be the existence of a three vertices of degree 1 with a common neighbour. Definev0G=minF:G−F has no isolated vertices and has 3 leaves adjacent to the same vertex}.Proposition 2 (see [7]).
An odd graphG has mp1G≤v0G.For odd vertices bipartite graphG=U∪V,E, we have v0′G=minF:G−F has no isolated vertices and has 2 leaves adjacent to the same vertex in V}.Proposition 3 (see [7]).
LetG be a bipartite graph with an odd number of vertices. Then, mp1G≤v0′G.IfH is a spanning subgraph of G, we want to know whether we have mp1H≤mp1G holds.Remark 1.
For an even numbernn≥12, let G be a graph obtained from a K3=u1v1w1u1 and a clique Kn−3 by adding three edges u1u2,v1v2,w1w2, where u2,v2,w2∈VKn−3. Let H be a graph obtained from G by deleting three edges of K3. It is clear that H is a spanning subgraph of G. By deleting three edges u1u2,v1v2,w1w2 in G, we can see that there is no perfect matching in the resulting graph; hence, mp1G≤3. From the definition of mp1H, for any X⊆EH, to avoid isolated vertices in H−X, we have X∩u1u2,v1v2,w1w2=∅ and X⊆EKn−3, so mp1H≥4>3≥mp1G.Remark 2.
For an odd numbernn≥15, let G be a graph obtained from a clique K4 with vertex set u1,v1,w1,t1 and a clique Kn−4 by adding four edges u1u2,v1v2,w1w2,t1t2 between them, where u2,v2,w2,t2∈VKn−4. Let H be a graph obtained from G by deleting six edges of the K4. By deleting u1u2,v1v2,w1w2,t1t2 and three edges in EK4, we can find there no perfect matching in the resulting graph; hence, mp1G≤7. For any X⊆EH, to avoid isolated vertices in H−X, we have X∩u1u2,v1v2,w1w2,t1t2=∅ and X⊆EKn−4, so mp1H≥8>7≥mp1G.


## 2. Sharp Bounds for CMP Number

Lemma 1 (see [2]).
Letn≥2. Then, mpKn,n=n, Kn,n is super matched.Lemma 2.
(see [19]). Let n≥3. Then, mp1Kn,n=2n−2, Kn,n is conditionally super matched.Theorem 1.
(see [19])(1)
Letn≥4 be even, then(1)mp1Kn=n2+2n8,ifn∈4,6,8,2n−5,ifn≥10.(2)
Letn≥5 be odd, then(2)mp1Kn=n2+4n+38,ifn∈5,7,9,11,13,3n−9,ifn≥15.Proposition 4.
LetG be a graph with an even number of vertices and δ≥3. Then, mp1G≤δ+∆−2.Proof.
Letu be the minimum-degree vertex in G. Since δG≥3, it exists a path u−v−w in G. Let X=Eu,w,NGu,w∖v, then G−X exists a path u−v−w and dGu=dGv=1. By Proposition 1, mp1G≤du+dw−2≤δ+∆−2.
By Lemma2, mp1Kn,n=2n−2, ∆Kn,n=δKn,n=n, we get δKn,n+∆Kn,n−2=2n−2 for n≥3.Proposition 5.
LetG be a graph with an odd number of vertices and δ≥4. Then, mp1G≤δ+2∆−3.Proof.
Letu be the minimum-degree vertex of G and ux∈EG. Since dx≥4, there exist two vertices v, w and two edges xv,xw∈EG. Let X=Eu,v,w,NGu,v,w∖x, then G−X has no isolated vertices and has 3 leaves adjacent to the same vertex x. By Proposition 2, mp1G≤du+dv+dw−3≤δ+2∆−3.


## 3. Graphs with Given CMP Numbers

Theorem 2 (see [20]).
For a graph with ordern, if δ≥n/2, then G is Hamiltonian.Lemma 3 (see [19]).
A graphG has a perfect matching if and only if G satisfies Tutte’s condition, that is, oG−S≤S.Lemma 4 (see [19]).
A graphG has an almost-perfect matching if and only if every subset vertices satisfies Berge’s condition, that is, oG−S≤S+1.The graphs withmp1G=2n−kk≥5 can be characterized completely.Proposition 6.
The even graphG has order of n≥10, and δG≥3. Then, mp1G=2n−5 if and only if G≅Kn.Proof.
From Theorem1, we know mp1G=2n−5 when G is a complete graph. Conversely, if mp1G=2n−5 and G≇Kn, then there exist uv∉EG. If w is a common neighbour vertex of u,v, let X=EGu,v,NGu,v∖w. So there exists a path u−w−v in G−X satisfies dGu=dGv=1. Since δG≥3, G−X has no isolated vertices and no perfect matching exist. Since X=dGu+dGv−2≤2n−6, it means mp1G≤X≤2n−6, which contradicts to mp1G=2n−5. If no exist a common neighbour vertex for u and v, we choose a shortest path between u and v, say P:=ua1a2…asvuas∉EG. Let X=EGu,a2,NGu,a2∖a1, then there exists a path u−a1−a2 in G−X and dGu=dGa2=1. Since X=du+da2−2≤n−3+n−2−2=2n−7, then mp1G≤X≤2n−7. So G≅Kn.Theorem 3.
An even graphG has order n≥8k−12 and δG≥3. Then, mp1G=2n−k if and only if δG=n+4−k and 5≤k≤n+1.Proof.
From Proposition6, we only need to consider 6≤k≤n+1. When mp1G=2n−k, we first suppose δG≤n+3−k and choose a minimum-degree vertex u. Since δG≥3, there exists a path u−v−w in G. Let X=Eu,w,NGu,w∖v, then there exists a path u−v−w in EG−X and du=dv=1. If uw∈EG, then X≤n+3−k−2+n−1−2+1=2n−k−1, and we have mp1G≤X≤2n−k−1. If uw∉EG, then X≤n+3−k−1+n−1−2=2n−k−1, and we have mp1G≤X≤2n−k−1. Thus, δG≥n+4−k. Let δG≥n+4−k, and let δG=n+4−k+t and t≥1. By induction on k, we prove that mp1G=2n−k if and only if δG=n+4−k. From Proposition 6, the result holds for k=5. Suppose that the argument is true for every integer k′k′<k, that is, mp1G=2n−k′ if and only if δG=n+4−k′. Since δG=n+4−k+t=n+4−k−t and k−t<k, then mp1G=2n−k−t, it contradicts to mp1G=2n−k. So δG=n+4−k.
Conversely, supposeδG=n+4−k. We prove that mp1G=2n−k. Let u∈VG. Since δG≥3, it follows that there exists a path u−v−w in G. Let X=Eu,w,NGu,w∖v, then EG−X exists a path u−v−w and du=dw=1. If uw∈EG, then X≤n+4−k−2+n−1−2+1=2n−k, and we have mp1G≤X≤2n−k. If uw∉EG, then X≤n+4−k−1+n−1−2=2n−k, and we have mp1G≤X≤2n−k. Thus, mp1G≤2n−k.
Now, we prove thatmp1G≥2n−k. Suppose degGXv≤n/2+4−k for every v∈VG, degG−Xv=degGv−degGXv≥n+4−k−n/2−4+k=n/2. By Theorem 2, G−X has a Hamiltonian cycle, so there is a perfect matching in G−X. It exists a vertex v∈VG and degGXv≥n/2+5−k. Since G−X has no isolated vertices, there has a vertex u∈VG and one edge vu∈EG\X. Let G1=G−v,u, then X∩EG1≤2n−k−1−n/2+5−k=3n/2−6.
IfG1−X has an isolated vertex, say a, then dG1Xa≥n+2−k. Since G−X has no isolated vertices, it means a must adjacent to at least one of u and v. If av∈EG−X, let G2=G−v,a, then X∩EG2≤X−degGXv−degGXa≤2n−k−1−n/2+5−k−n+2−k=n/2+k−8. Clearly, degG2−Xx+degG2−Xy≥2n+2−k−n/2−k+8=3n/2−3k+12≥nn≥6k−14 for any vertex pairs x,y∈VG2, and then, G2−X contains a Hamiltonian cycle and a perfect matching M. Furthermore, M∪av is a perfect matching of G−X. If av∉EG−X, then au∈EG−X. If there is a vertex b and b≠u such that vb∈EG−X, we let G3=G−v,b,u,a. Clearly, degG3−Xs+degG3−Xt≥2n−k−n/2−k+8−1=n+n/2−3k+7≥n+6k−14/2−3k+7=n (n≥6k−14) for any vertex pairs s,t∈VG3, and then, G3−X has a Hamiltonian cycle and a perfect matching M in G3−X. Furthermore, M∪vb,ua is a perfect matching of G−X. If there exists no vertex b (except u) such that vb∈EG−X, let X1=Ev,NGv∖u∪Ea,NGa∖u, we have X1⊆X and 2n+6−2k≤X1≤2n−6. So X−X1≥2n−k−1−2n+6=5−k≥0, it means k≤5, which contradicts to k≥6.
IfG1−X has no isolated vertices, suppose gG1Xx≤n/2+2−k for every vertex x∈VG1, then degG1−Xx=degG1x−degG1Xx≥n+2−k−n/2−2+k=n/2. Then, G1−X contains a Hamiltonian cycle, so a perfect matching M in G1−X, and then, M∪uv is a perfect matching in G−X. Suppose that there exist two vertices x,y∈VG1 with degG1Xx≥n/2+3−k such that xy∉X. Let G3=G−v,u,x,y, then EG3∩X≤3n/2−6−n/2−3+k=n+k−9. Since dG3−Xa≥n−k−n−k+9=9>1 for each vertex a∈VG3, G3−X has no isolated vertices. Suppose degG3Xx′≤n/2−k for every vertex x′∈VG3, then degG3−Xx′=degG3x′−degG3Xx′≥n−k−n/2+k=n/2. By Theorem 2, G3−X contains a Hamiltonian cycle and a matching M in G3−X, so M∪uv,xy is a perfect matching in G−X. Suppose that there exists a vertex x′∈VG3 and degG3Xx′≥n/2+1−k and x′y′∉X. Let G4=G−v,u,x,y,x′,y′. EG4∩X≤n+k−9−n/2−1+k=n/2+2k−10. It follows that for any vertex pair s,t∈VG4, degG4−Xs+degG4−Xt≥2n−2−k−n/2+10−2k=3n/2−4k+6≥n. n≥8k−12. So G4−X contains a Hamiltonian cycle, and hence, there is a perfect matching M in G4−X. Clearly, M∪uv,xy,x′y′ is a perfect matching of G−X. From the above argument, we get mp1G=2n−k.
Next, we characterize the odd graphs withmp1G=3n−9,3n−10,3n−11, respectively.Proposition 7.
LetG be an order n≥15 and δG≥4. Then, mp1G=3n−9 if and only if G is Kn.Proof.
Supposemp1G=3n−9, but G≠Kn. It exists two vertices u and v such that uv∉EG. If they have a common neighbourhood w, then there is a vertex a such that wa∈EG by δG≥4. Let X=Eu,v,a,NGu,v,a∖w, then X≤n−2−2+n−2−2+n−1−3+2=3n−10 and u,v,a are three vertices of degree 1 with common neighbour w in EG−X. From δG≥4, that G−X has no isolated vertices, and X is a basic obstruction set to an almost-perfect matching of G. Thus, mp1G≤X≤3n−10, and it contradicts to mp1G=3n−9. If u and v no common neighbourhood, choose a shortest path p=ua1a2⋅⋅⋅asv (uas∉EG) between u and v. By δG≥4, there exists another vertex b1 such that a1b1∈EG. Let X=Eu,a2,b1,NGu,a2,b1∖a1, then X≤n−2−2+n−2−2+n−1−3+2=3n−10 and u,a2,b1 are three vertices of degree 1 with the common neighbour a1 in EG−X. Thus, mp1G≤X≤3n−10, which contradicts to mp1G=3n−9.Proposition 8.
LetG be an odd graph of order n≥15 and δG≥4. Then, mp1G=3n−10 if and only if G=Kn−e, where e∈EKn.Proof.
IfG=Kn−e, e=uv∉EG. Choosing another two vertices x,y from VG, we know ux,vx,yx∈EG. Let X=Eu,v,y,NGu,v,y∖x, then X≤2n−2−4+n−1−3+2=3n−10 and u,v,y are three vertices of degree 1 with a common neighbour x in EG−X. It means that mp1G≤3n−10. For every X⊆EG with X=3n−11, G−X=Kn−e−X=Kn−X∪e is the graph which is obtained from Kn by deleting at most 3n−10 edges. By Proposition 7, G−X has an almost-perfect matching, so mp1G≥3n−10. By above argument, mp1G=3n−10.
Conversely, it shows thatG=Kn−e when mp1G=3n−10. If G≠Kn−e, then G¯ contains a path P3=uvw or two independent edges xy,uv as its subgraph. For the former case, if u,v,w have a common neighbour a, let X=Eu,v,w,NGu,v,w∖a, we have X≤2n−2−2+n−1−3+1=3n−11 and u,v,w are three vertices of degree 1 in EG−X, and G−X has no isolated vertices since δG≥4. It follows that mp1G≤X≤3n−11. If u,v,w have no common neighbour, it means that degGx≤n−2 for any vertex x∈VG∖u,v,w. Since δG≥4, there exists a vertex a∉u,w such that va∈EG; furthermore, there are two vertices b1,b2 such that ab1,ab2∈EG. Let X=Ev,b1,b2,NGv,b1,b2∖a, then X≤n−3−3+2n−2−3+3=3n−13 and v,b1,b2 are three vertices of degree 1 with common neighbour a in G−X. From δG≥4, we know G−X has no isolated vertices. Thus, mp1G≤X≤3n−13, a contradiction.
For the case of two independent edgesxy,uv∈EG¯, there are three situations to be considered. If there are three vertices in x,y,u,v with a common neighbour a, without loss of generality, they are x,y,u have a common neighbour. Let X=Ex,y,u,NGx,y,u∖a, then X≤n−2−3+2n−2−2+2=3n−11 and v,y,u are three vertices of degree 1 in G−X. If there are two vertices in x,y,u,v with a common neighbour a, then there is a vertex a′a′≠x,y such that aa′∈EG. Clearly, a′ is connected to at most two of vertices in x,y,u,v; thus, degGa′≤n−3. Let X=Ex,y,a′,NGx,y,a′∖a, so x,y,a′ are three vertices of degree 1 with common neighbour a in G−X and X≤n−3−3+2n−2−2+2=3n−12. If any two vertices of x,y,u,v have no common neighbour, it means for every vertex a∈VG∖x,y,u,v is connected to at most one of vertices in x,y,u,v, so degGa≤n−4. Choose a vertex a (a≠y) and xa∈EG, then a must has two other adjacent vertices a1,a2. Let X=Ex,a1,a2,NGx,a1,a2∖a, then X≤n−2−3+2n−4−3+3=3n−16 and x,a1,a2 are three vertices of degree 1 in G−X. It is a contradiction. Together with the above argument, we can find G=Kn−e.Proposition 9.
LetG has n≥25 and δG≥4. Then, mp1G=3n−11 if and only if one of the following conditions holds.(1)
δG=n−2 and G≠Kn−e(2)
G=Kn−EP3Proof.
Supposemp1G=3n−11. Then, we claim δG≥n−3. Assume, on the contrary, that δG≤n−4. Then, there exists a vertex u in G such that dGu≤n−4. Choose v∈NGu and a,b∈NGv, since δG≥4. Let X=Eu,a,b,NGu,a,b∖v, so u,a,b are three vertices of degree 1 with common neighbour v in G−X and X≤n−4−3+2n−1−3+3=3n−12. Thus, mp1G≤X≤3n−12, which contradicts mp1G=3n−11. By Propositions 7 and 8 and δG≥n−3, we have δG=n−2 and G≠Kn−e or δG=n−3.
WhenδG=n−3, we need to show G=Kn−EP3. Assume degGu=n−3. It means there exist two vertices v,w such that uv,uw∉EG and ux∈EG for every vertex x∈VG∖w,v. Assume, on the contrary, that G≠Kn−EP3. Except uv,uw∉EG, there exists two vertices x, y in VG and xy∉EG. If x=v, then degGv=n−3. Choose va∈EG and ab∈EG; clearly, ua∈EG. Let X=Eu,v,b,NGu,v,b∖a, so u,v,b are three vertices of degree 1 with common neighbour a in G−X and X≤n−1−3+2n−3−2+2=3n−12. mp1G≤X≤3n−12, So x,y∉v,w. Since δG≥4, choose xa,ab∈EG and ux,ua,ub⊆EG. Let X=Eu,x,b,NGu,x,b∖a, so u,x,b are three vertices of degree 1 with common neighbour a in G−X and X≤n−3−3+n−2−3+n−1−3+3=3n−12. mp1G≤X≤3n−12, which is a contradiction. In summary, we have G=Kn−EP3, or δG=n−2 and G≠Kn−e, as required.
Conversely, by Propositions7 and 8, we have mp1G≤3n−11. We show mp1G≥3n−11. If G=Kn−EP3, for every X⊆EG with X≤3n−12, it follows that G−X=Kn−X∪EP3 is a graph obtained from Kn by deleting at most 3n−10 edges. By Proposition 7, G−X has an almost-perfect matching, as desired. If δG=n−2 and G≠Kn−e, then G=Kn−L, where L is a matching of Kn of size at least 2. It suffices to prove that G−X has an almost-perfect matching for every X⊆EG with X≤3n−12 such that G−X has no isolated vertices. Suppose any vertex v∈VG has degGXv≤n−5/2, then degG−Xv=degGv−degGXv≥n−2−n−5/2=n+1/2>n/2. By Theorem 2, G−X contains a Hamiltonian cycle. So an almost-perfect matching in G−X, a contradiction. Now, we suppose that there exists a vertex v∈VG and degGXv≥n−3/2. Since G−X has no isolated vertices, it follows that there exists a vertex u∈VG and vu∈EG−X. Let G1=G−v,u, then X∩EG1≤3n−12−n−3/2=5n−21/2.
IfG1−X has no isolated vertices, suppose every vertex x∈VG1 has degGXx≤n−9/2. Then, degG1−Xx=degG1x−degG1Xx≥n−4−n−9/2=n+1/2. By Theorem 2, G1−X contains a Hamiltonian cycle. So an almost-perfect matching M′ in G1−X and M′∪uv is an almost-perfect matching in G−X, a contradiction.
We suppose that there exists a vertexx∈VG1 and degG1Xx≥n−7/2 and xy∉X. Let G2=G−v,u,x,y, then EG2∩X≤5n−21/2−n−7/2=4n−14/2. Recall that G=Kn−L, where L is a matching of Kn of size at least 2; thus, G2=Kn−L−u,v,x,y=Kn−4−L. It means removing up to n−5/2 edges from Kn−4. Since n≥25, n−5/2+4n−14/2=5n−19/2<3n−4−9. By Proposition 7, G2−X has an almost-perfect matching M′, and M′∪uv,xy is an almost-perfect matching of G−X.
IfG1−X has two isolated vertices a and b, then 3n−12−degXv−degXa−degXb≤3n−12−n−3/2−2n−4=n−5/2. Since G−X has no isolated vertices, the vertices a and b must be at least adjacent to one of u,v, respectively. Since δ=n−2, we can assume au∈EG and bv∈EG. Let G2=G−u,v,a,b=Kn−L−u,v,a,b. Since n−5/2+n−5/2=n−5, mp1Kn−4=3n−4−9=3n−21 and n−5<3n−21. So G2−X has an almost-perfect matching M′, and M′∪au,bv is an almost-perfect matching of G−X.
IfG1−X has one isolated vertex a, then degGXa≥n−4. Let G2=G−u,v,a, clearly, EG2∩X≤3n−12−n−3/2−n+4=3n−13/2. Suppose that every vertices b∈VG2 have degG2Xb≤n−9/2, then degG2−Xb=degG2b−degG2Xb≥n−5−n−9/2>n−3/2. By Theorem 2, G2−X contains a Hamiltonian cycle. So there is a perfect matching M in G2−X, and M∪uv is an almost-perfect matching in G−X missing a. We suppose that there exists a vertex b∈VG2 and degG2Xb≥n−7/2. Since G1−X has only one isolated vertex a, it follows that there exists one vertex b′ and bb′∉X. Let G3=G−v,u,a,b,b′, then EG3∩X≤3n−13/2−n−7/2=n−3. Clearly, G3=Kn−L−v,u,a,b,b′ and VG3=n−5 is even, and we have mp1Kn−5=2n−15. Since Kn−5−L means from Kn−5 remove at most n−5/2 edges and n−5/2+n−3=3n−11/2<2n−15 (n≥25), G3−X has a perfect matching M, and M∪uv,bb′ is an almost-perfect matching of G−X missing a, a contradiction. Thus, mp1G=3n−11.


## 4. Extremal Problems on CMP Number

Consider the three extremal problems in the introduction.Lemma 5.
Letn,k be two positive integers and n≥3 be odd. Then,(1)
sn,0=0(2)
sn,1=n+5/2(3)
sn,2=n+7/2Proof.
(1)
LetG be a no edges with order n graph. Clearly, mp1G=0. So sn,0=0.(2)
LetH=n−5/2P2∪S5+, where S5+ is a graph obtained from a star K1,4 by adding one edge between two leaves. Clearly, mp1H=1 and H has n+5/2 edges. Then, sn,1≤n+5/2. Conversely, assume that sn,1≤n+3/2, it means exists an odd graph G of order n with sn,1≤n+3/2 thus mp1G=1. Assume that C1,C2,⋅⋅⋅,Ct are the connected components in G. If two of C1,C2,⋅⋅⋅,Ct are odd components in G, then mp1G=0. So there is exactly one odd component in G, suppose it is Ct. We may assume VC1≥VC2≥⋅⋅⋅≥VCt−1. If VC2≥4, then EG≥24−1+n−8−3/2+3−1=n+5/2, it contradicts with EG=sn,1≤n+3/2. Then, VC1≥4 and VC2=VC3=⋅⋅⋅=VCt−1=2. If VC1≥6, then EG≥6−1+n−6−3/2+3−1=n+5/2, a contradiction. So VC1=4 or VC1=2. If VC1=4, we claim VCt=3. Otherwise, VCt≥5 and EG≥4−1+n−4−5/2+5−1=n+5/2. We have n−7/2P2 in G, and EC1+ECt≤n+3/2−n−7/2=5. So G=n−7/2P2∪P3∪P4 or G=n−7/2P2∪P3∪S4. For two cases, we know mp1G=0. If VC1=2, we claim VCt=5. Otherwise, VCt=3 or VCt≥7. If VCt=3, then ECt≤n−3/2−n−3/2=3 and ECt≥2. So G=n−3/2P2∪C3 or G=n−3/2P2∪P3. For two cases, we know mp1G=0. If VCt≥7, then EG≥6+n−7/2=n+5/2, which is a contradiction. So VCt=5, and ECt≤n+3/2−n−5/2=4. Thus, G=n−5/2P2∪P5 or G=n−5/2P2∪S5. For two cases, we know mp1G=0. So sn,1=n+5/2.(3)
LetH=n−7/2P2∪P3∪K4−e. Clearly, mp1H=2 and H has n+7/2 edges. Then, sn,2≤n+7/2. Since sn,1=n+5/2, it follows that n+5/2≤sn,1≤sn,2≤n+7/2. Now, we prove sn,2≥n+7/2. If we assume that sn,2=n+5/2, then it exists an odd graph G of order n with sn,2=n+5/2 such that mp1G=2. So G is not connected. Let C1,C2,⋅⋅⋅,Ct be the connected components in G. If two of C1,C2,⋅⋅⋅,Ct are odd components, then mp1G=0. So there is exactly one odd component in G, and we can assume that VCt is odd and VCi is even for 1≤i≤t−1. Assume VC1≥VC2≥⋅⋅⋅≥VCt−1. If VCt≥9, then EG≥VCt−1+n−VCt/2=VCt+n−2/2≥n+7/2, but EG=n+5/2. So 3≤VCt≤7. Now, we consider three cases of the number of VCt. First assume VCt=7, if VC1≥4, then EG≥6+3+n−7−4/2=n+7/2, a contradiction. All even components are P2, and ECt=n−5/2−n−7/2=6. By VCt=7 and ECt=6, the structure of Ct must be P7 or P6 add one pendant edge or P5 add two pendant edges. For above three structure of Ct, we have mp1G=0 or mp1G=1. Next assume VCt=5, if VC1≥4, then EG≥4+3+n−9/2=n+5/2. Since EG=n+5/2, So VC1=4 and VC2=VC3=⋅⋅⋅=VCt−1=2. Since Ct has an almost-perfect matching, so Ct must be P5 or P4 add one pendant edge. For any structure of Ct, mp1G=0. At last, VCt=3 If VC2≥4, then EG≥2+24−1+n−8−3/2=n+5/2. Since EG=n+5/2. So G=n−11/2P2∪2P4 and mp1G=0. So only have VC1≥4, other even components are P2. If VC1≥6, then EG≥5+2+n−6−3/2=n+5/2. Since EG=n+5/2. It follows that Ct=P3, so C1 must be P6 or P5 add one pendant edge or P4 add two pendant edges. For above structure of Ct, mp1G=0 or mp1G=1. If VC1=4, then EC1∪Ct=n+5/2−n+7/2=6. So EC1=2 and ECt=4, or EC1=3 and ECt=3. It follows that G=n−7/2P2∪P3∪C4 or G=n−7/2P2∪P3∪S3+ or G=n−7/2P2∪C3∪P4. For any case, we know mp1G=0 or mp1G=1. So sn,2=n+7/2.Theorem 4.
Letn≥5 be an odd integer, 3≤k≤3n−9. Then,(1)
Ifk−3/3 is odd, then(3)sn,k≤k−3/32+n+2+2k2.(2)
Ifk−3/3 is even, then(4)sn,k≤k−3/32+2k−3/3+2k+3+n2.Proof.
(1)
LetH1 be a graph obtained from u, K3, Kk−3/3, by arbitrarily adding k−3 edges between K3 and Kk−3/3, and making the join graphs: u∨K3 and u∨Kk−3/3. Let H=H1∪n−4−k−3/3/2P2. Suppose v1,v2,v3 are three vertices in K3, the degree of v1,v2,v3 in H1 is less than or equal to the degree of other vertices in VH1\v1,v2,v3. Clearly, we delete k−3 edges between K3 and Kk−3/3 and three edges in K3 of H, and then, v1,v2,v3 are three vertices of degree 1 with the common neighbour u and the rests of H have no isolated vertices. And EH=3+k−3/3+k+k−3/3/2+n−4−k−3/3/2=k−3/32+n+2+2k/2, so sn,k≤k−3/32+n+2+2k/2.(2)
LetH1 be a graph obtained from tree cliques u, K3, Kk−3/3+1. By arbitrarily adding k−3 edges between K3 and Kk−3/3+1, then make the join graphs: u∨K3 and u∨Kk−3/3+1. Let H=H1∪n−5−k−3/3/2P2. The degree of three vertices v1,v2,v3 in K3 is less than or equal to the degree of other vertices in VH1\K3. Clearly, when we delete k−3 edges between K3 and Kk−3/3 and three edges in K3, then v1,v2,v3 are three vertices of degree 1 with common neighbour u, and the rest of graphs have no isolated vertices. This just deletes the k edges from H and no almost-perfect matching in result graph.EH=3+k−3/3+1+k+k−3/3+12+n−5−k−3/3/2=k−3/32+2k−3/3+2k+3+n/2, so sn,k≤k−3/32+2k−3/3+2k+3+n/2.Lemma 6.
Letn,k be two positive integers and n≥4 be even. Then,(1)
sn,0=0(2)
sn,1=n/2+2(3)
sn,2=n/2+3(4)
sn,3=n/2+4Proof.
(1)
LetG be the graph of order n with no edges. Clearly, mp1G=0. So sn,0=0.(2)
LetH=n−4/2P2∪S4+. S4+ is a star of order 4 and add one edge between two of pendent vertices. Clearly, mp1H=1 and H has n/2+2 edges. Then, sn,1≤n/2+2. Conversely, assume that sn,1≤n/2+1. Then, there exists an even graph G of order n with sn,1≤n/2+1 edges such that mp1G=1. Because G exists a perfect matching, so EG≥n/2. If EG=n/2, then G=n/2P2 and mp1G=0. If EG=n/2+1, then G=n−4/2P2∪P4 and mp1G=0. So sn,1=n/2+2.(3)
LetH=K4−e∪n−4/2P2. Clearly, mp1H=2 and H has n/2+3 edges. Then, sn,2≤n/2+3. Since sn,1=n/2+2, it follows n/2+2=sn,1≤sn,2≤n/2+3. Assume that sn,2=n/2+2. Then, there exists an even graph G of order n with sn,2=n/2+2 edges such that mp1G=2. Because G has a perfect matching, so EG≥n/2, now G is a graph of add two edges to a perfect match of size n/2. So G has the following situations: G=C4∪n−4/2P2, G=P6∪n−6/2P2, G=2P4∪n−8/2P2, G=K3+∪n−4/2P2, G=n−6/2P2∪P5 add one pendant edge on the middle vertex), and for any of the above, we have mp1G=0 or mp1G=1. So sn,2=n/2+3.(4)
LetH=K4∪n−4/2P2. Clearly, mp1H=3 and H has n/2+4 edges. Then, sn,3≤n/2+4. Since sn,2=n/2+3, it follows that n/2+3=sn,2≤sn,3≤n/2+4. Assume that sn,3=n/2+3. Then, there exists an even graph G of order n with sn,3=n/2+3 edges such that mp1G=2. Since G has a perfect matching, so G is a graph of add three edges to a perfect match of size n/2. All possible structures of G are shown as follows (Figure 1). For any structure, we have mp1G=0 or mp1G=1 or mp1G=2. So sn,3=n/2+4.Theorem 5.
Letn,k be two positive integers and n≥6 be even and 4≤k≤2n−5. Then,(1)
Ifk−1/2 is odd, then sn,k≤k−1/22+n+2k+1/2(2)
Ifk−1/2 is even, then sn,k≤k−1/22+2k−1/2+n+2k+2/2Figure 1
All possible structures ofG.Proof.
(1)
LetH1 be a graph obtained from K3=u1u2u3 and Kk−1/2. add k−1 edges between {u2,u3} and Kk−1/2, then make the join graph: u1∨Kk−1/2. Let H=H1∪n−3−k−1/2/2P2. And the degree of three vertices u2,u3 in K3 is less than or equal to the degree of other vertices in VH1\u2,u3. Clearly, when we delete edge u2u3 and k−1 edges between {u2,u3} and Kk−1/2, then u2,u3 are two vertices of degree 1 with common neighbour u1, and the rest of the graphs have no isolated vertices. This just deletes the k edges from H and no perfect matching in result graph. EH=2+k−1/2+k+k−1/22+n−3−k−1/2/2=k−1/22+n+1+2k/2, so sn,k≤k−1/22+n+1+2k/2.(2)
LetH1 be a graph obtained from K3=u1u2u3 and Kk−1/2+1. Arbitrarily add k−1 edges between {u2,u3} and Kk−1/2+1, then make the join graph: u1∨Kk−1/2+1. Let H=H1∪n−4−k−1/2/2P2. From the construction of graph H1, the degree of three vertices u2,u3 in K3 is less than or equal to the degree of other vertices in VH1\u2,u3. Clearly, when we delete edge u2u3 and k−1 edges between {u2,u3} and Kk−1/2+1, then u2,u3 are two vertices of degree 1 with common neighbour u1, and the rest of the graphs have no isolated vertices. This just deletes the k edges fromH and no perfect matching in result graph. EH=3+k−1/2+k+k−1/2+12+n−4−k−1/2/2=k−1/22+2k−1/2+n+2+2k/2, so sn,k≤k−1/22+2k−1/2+n+2+2k/2.Observation 1.
gn,k=sn,k+1−1, n,k be two positive integers.Corollary 1.
Letn,k be two positive integers and n≥5 be odd, 3≤k≤3n−9. Then,(1)
Ifk−3/3 is odd, then gn,k≤k−2/32+n+2k+2/2(2)
Ifk−3/3 is even, then gn,k≤k−2/32+2k−2/3+2k+3+n/2Corollary 2.
Letn≥6, 4≤k≤2n−5 be two positive integers and be even. Then,(1)
Ifk−1/2 is odd, then gn,k≤k/22+n+2k+1/2(2)
Ifk−3/3 is even, then gn,k≤k/22+2k/2+n+2k+2/2Theorem 6.
Letn,k be two positive integers. Then,(1)
Ifn≥10 is even and 1≤k≤2n−5, then fn,k=n−32+k+n−1(2)
Ifn≥15 is odd and 1≤k≤3n−9, then fn,k=n−42+k+n−1Proof.
(1)
First showfn,k≥n−32+k+n−1, we construct H as follows, give three components H1=P3=v1v2v3, H2=Kk−1/2, H3=Kn−3−k−1/2. k−1edges are connected between v1,v3 and H2, v2 adjacents to all vertices in H2 and H3, and then make a join between H2 and H3. Clearly, H is a connected graph on n vertices, EH=2+k−1+n−3+n−32=n−32+k+n−2, and mp1H=k−1<k. So fn,k≥n−32+k+n−1. Now to show fn,k≤n−32+k+n−1, let G be a graph with n vertices such EG≥n−32+n+k−1. For any X⊆EG, X=k−1, so EG−X≥n−32+n and EG−X¯≤n2−n−32−n=2n−6. Since mp1Kn=2n−5 by Theorem 1, thus G−X has a perfect matching, and hence, mp1H≥k. So fn,k=n−32+k+n−1.(2)
First provefn,k≥n−42+k+n−1, we construct H as follows: give three components H1,H2,H3. H1is a star graph with central vertex u and three pendant vertices v1,v2,v3. H2=Kk−1/3, H3=Kn−4−k−1/3. k−1 edges are connected between v1,v2,v3 and H2, u adjacent to all vertices in H2 and H3 and then make a join between H2 and H3. Clearly, H is a connected graph on n vertices, EH=3+k−1+n−4+n−42=n−42+k+n−2, and mp1H=k−1<k. So fn,k≥n−42+k+n−1. Now to show fn,k≤n−42+k+n−1, let G be a graph with n vertices such EG≥n−42+n+k−1. For any X⊆EG, X=k−1, so EG−X≥n−42+n and EG−X¯≤n2−n−42−n=3n−10. Since mp1Kn=3n−9, tt follows that G−X has an almost-perfect matching, and hence, mp1H≥k. So fn,k=n−42+k+n−1.


## 5. Conclusion

The concept of matching preclusion was introduced in [2]. The matching preclusion number measures the robustness of a graph as a communications network topology. In a network, a vertex with a special matching vertex after edge failure any time implies that tasks running on a fault vertex can be change into its matching vertex. Larger mpG signifies higher fault tolerance. However, the probability that the adjacent vertices of the same vertex fail at the same time is very small. In the paper, we mainly want to discuss the conditional matching preclusion number of general graphs. First of all, we want to discuss the bound of the conditional matching preclusion number of a general graph. It is necessary to discuss the bounds of reaching the number of conditional matches according to the parity of the number of vertices of the graph. Next, we will draw a graph from the conditional matching preclusion number. When the number of conditional matches is a special value, what property does the obtained graph satisfy. From the perspective of graph description, this is very meaningful. Finally, we discussed three extreme value problems. It is actually an extension of the two problems discussed previously, but it is more difficult to solve than the previous problems.



---

*Source: 5571724-2023-02-21.xml*