betaFeedback

WorksMathematics

Clique counts under degree and matching constraints

Abstract

We study the maximum number of tt-cliques in graphs with maximum degree at most DD and matching number at most MM, with no restriction on the number of vertices. For t≥3t\ge 3, we determine this maximum whenever D≥2M−1D\ge 2M-1 and characterize all extremal graphs when the maximum is positive. Up to isolated vertices, these are complete or complete split graphs for D≥2MD\ge 2M, while K2MK_{2M} is uniquely extremal when D=2M−1D=2M-1. We also derive a general upper bound from the Chvátal-Hanson edge theorem and refine it for even DD. For fixed even DD and 3≤t≤D+13\le t\le D+1, every extremal graph consists, apart from isolated vertices, of copies of KD+1K_{D+1} together with a remainder whose order is bounded independently of MM. When D/2D/2 divides MM, this remainder is empty and the extremal graph is unique. This structure yields an eventual recurrence, reducing the determination of all extremal values and graphs to finitely many matching bounds.

Introduction

Extremal graph theory studies how large a specified subgraph count can be under certain structural restrictions. For graphs of fixed order, Wang [4] extended the Erdős-Gallai matching theorem to clique counts, while Chao and Dong [2] gave a unified proof of the Gan-Loh-Sudakov conjecture for clique counts under a maximum-degree constraint. Under the simultaneous restrictions of bounded maximum degree and matching number, Chvátal and Hanson [3] determined the maximum number of K2K_2’s, that is, edges. Balachandran and Khare [1] subsequently gave a structural proof of the same formula. In this paper, we study the corresponding problem for larger cliques under both constraints, without imposing any restriction on the order of the graph.

All graphs considered are finite and simple. Let Δ(G)\Delta(G) and ν(G)\nu(G) denote the maximum degree and matching number of a graph GG, respectively, and let kt(G)k_t(G) be its number of tt-vertex cliques, counted by their vertex sets. We consider

Ft(D,M)=max⁡{kt(G):Δ(G)≤D, ν(G)≤M}.F_t(D, M) = \max\{k_t(G) : \Delta(G) \le D,\ \nu(G) \le M\}.

The endpoints of a maximum matching form a vertex cover of size at most 2M2M, so ∣E(G)∣≤2DM|E(G)| \le2DM. After isolated vertices are deleted, this also gives ∣V(G)∣≤4DM|V(G)| \le4DM, and hence the maximum exists. Clearly, Ft(D,0)=0F_t(D, 0) = 0 for t≥2t \ge2. We use the convention that (nj)=0\binom{n}{j} = 0 for n≥0n \ge0 whenever j<0j < 0 or j>nj > n.

The parameters Δ(G)<d\Delta(G) < d and ν(G)<m\nu(G) < m used by Balachandran and Khare [1] correspond to D=d−1D = d - 1 and M=m−1M = m - 1. For larger cliques, the edge maximum alone need not identify the extremal graphs.

In Theorems 2.1 and 3.1, we determine Ft(D,M)F_t(D,M) for D≥2M−1D \ge2M-1 and characterize the extremal graphs. We also give a general upper bound and improve it for even DD (Theorems 4.1 and 4.3). In the even-degree case, Theorem 4.4 gives a bounded-remainder description of the extremal graphs, from which Corollary 4.5 derives an eventual recurrence.

Let SD,M=KM∨KD+1−MS_{D,M}=K_M \vee K_{D+1-M}, where ∨\vee denotes the join. If D≥2MD \ge2M, both K2M+1K_{2M+1} and SD,MS_{D,M} have matching number MM and maximum degree at most DD. Put

At(M)=(2M+1t),Bt(D,M)=(Mt)+(D+1−M)(Mt−1).(1)A_t(M)=\binom{2M+1}{t}, \qquad B_t(D,M)=\binom{M}{t}+(D+1-M)\binom{M}{t-1}. \tag*{(1)}

Clearly, At(M)=kt(K2M+1)A_t(M)=k_t(K_{2M+1}) and Bt(D,M)=kt(SD,M)B_t(D,M)=k_t(S_{D,M}).

Note that the cases when t>2M+1t>2M+1 or t>D+1t>D+1 are not interesting. This is because a clique of order at least 2M+22M+2 contains M+1M+1 matching edges itself, and on the other hand KD+2K_{D+2} contains vertices of degree D+1D+1. Thus, in either case, Ft(D,M)=0F_t(D,M)=0.

Tight bound when D≥2MD \ge2M

As our first result we determine Ft(D,M)F_t(D,M) throughout the range D≥2MD \ge2M, in which the largest clique allowed by the matching constraint is also allowed by the degree constraint.

Theorem 2.1. Let M≥1M \ge1, D≥2MD \ge2M, and 3≤t≤2M+13 \le t \le2M+1 be integers. Then

Ft(D,M)=max⁡{At(M),Bt(D,M)}.(2)F_t(D,M)=\max\{A_t(M),B_t(D,M)\}. \tag*{(2)}

The only extremal graph is K2M+1K_{2M+1} if At(M)>Bt(D,M)A_t(M)>B_t(D,M), and SD,MS_{D,M} if Bt(D,M)>At(M)B_t(D,M)>A_t(M), up to isolated vertices. If the two values are equal, these two graphs are the only extremal graphs.

Wang [4] proved that the maximum number of KtK_t’s in an nn-vertex graph with matching number at most MM is

max⁡{(2M+1t),(Mt)+(n−M)(Mt−1)}(n≥2M+1).\max\left\{\binom{2M+1}{t},\binom{M}{t}+(n-M)\binom{M}{t-1}\right\}\qquad(n\ge2M+1).

Our formula has the same form with nn replaced by D+1D+1. But this substitution is not a consequence of Wang’s theorem since a graph of maximum degree DD may have arbitrarily many vertices.

We first establish two counting lemmas for the proof of Theorem 2.1.

Definition 2.2. For a set S⊆V(G)S \subseteq V(G), let ct(G,S,≤j)c_t(G,S,\le j) and ct(G,S,≥j)c_t(G,S,\ge j) denote the numbers of tt-cliques having at most jj vertices outside SS and at least jj vertices outside SS, respectively.

Lemma 2.3. Let S⊆V(G)S \subseteq V(G) with ∣S∣=s|S|=s, and suppose that Δ(G)≤D\Delta(G) \le D and D≥2sD \ge2s. For every t≥3t \ge3,

ct(G,S,≤1)≤(st)+(D+1−s)(st−1).(3)c_t(G,S,\le1)\le\binom{s}{t}+(D+1-s)\binom{s}{t-1}. \tag*{(3)}

If s≥t−1s \ge t-1, equality implies that G[S]=KsG[S]=K_s, every vertex of SS has degree DD, and every vertex outside SS that has a neighbour in SS is adjacent to all of SS.

Proof. If s<t−1s<t-1, both sides of (3) are zero. Thus we will assume s≥t−1s \ge t-1, and for v∈Sv \in S put av=∣NG(v)∩S∣a_v=|N_G(v)\cap S|. Let c0c_0 and c1c_1 be the numbers of tt-cliques containing zero and one vertex outside SS, respectively. Counting the cliques containing each vertex of SS gives

tc0≤∑v∈S(avt−1),(t−1)c1≤∑v∈S(D−av)(avt−2).tc_0\le\sum_{v\in S}\binom{a_v}{t-1},\qquad(t-1)c_1\le\sum_{v\in S}(D-a_v)\binom{a_v}{t-2}.

For the second inequality, fix v∈Sv \in S and a neighbour u∉Su \notin S. The other t−2t-2 vertices must lie in NG(v)∩SN_G(v) \cap S, giving at most (avt−2)\binom{a_v}{t-2} choices. There are at most D−avD-a_v choices for uu. Define

f(a)=1t(at−1)+D−at−1(at−2).f(a)=\frac{1}{t}\binom{a}{t-1}+\frac{D-a}{t-1}\binom{a}{t-2}.

Therefore, we get ct(G,S,≤1)≤∑v∈Sf(av)c_t(G,S,\leq1) \leq\sum_{v\in S} f(a_v). For 0≤a≤s−20 \leq a \leq s-2, Pascal’s identity gives

f(a+1)−f(a)=D−a−1t−1(at−3)−1t(t−1)(at−2).f(a+1)-f(a)=\frac{D-a-1}{t-1}\binom{a}{t-3}-\frac{1}{t(t-1)}\binom{a}{t-2}.

Clearly this difference is zero if a<t−3a<t-3. Otherwise the difference is

1t−1(at−3)(D−a−1−a−t+3t(t−2)).\frac{1}{t-1}\binom{a}{t-3}\left(D-a-1-\frac{a-t+3}{t(t-2)}\right).

Recall that D≥2sD \geq2s, a≤s−2a \leq s-2 and t≥3t \geq3. Therefore, the bracket above evaluates to at least s+1−(s−2)/3>0s+1-(s-2)/3>0, and therefore the difference is positive. Thus f(a)≤f(s−1)f(a) \leq f(s-1), with equality only at a=s−1a=s-1. Therefore,

∑v∈Sf(av)≤sf(s−1)=(st)+(D+1−s)(st−1).\sum_{v\in S} f(a_v) \leq sf(s-1)=\binom{s}{t}+(D+1-s)\binom{s}{t-1}.

If equality holds then every av=s−1a_v=s-1, so G[S]=KsG[S]=K_s. Since (s−1t−2)>0\binom{s-1}{t-2}>0, equality in the bound for c1c_1 also forces every v∈Sv\in S to have exactly D−av=D−s+1D-a_v=D-s+1 neighbours outside $S. Since G[S]G[S] is a clique of order ss, every vertex in SS has degree (s−1)+(D−s+1)=D(s-1)+(D-s+1)=D. For each outside neighbour uu of vv, all (avt−2)=(s−1t−2)\binom{a_v}{t-2}=\binom{s-1}{t-2} possible choices must occur. As $1\leq t-2\leq s-1$, this requires uu to be adjacent to every vertex of S∖{v}S\setminus\{v\}. Therefore the equality conditions follow.

Lemma 2.4. Let r∈Z≥0r \in\mathbb{Z}_{\geq0}, and let HH be a graph with H1,…,HqH_1,\ldots,H_q as its components. Suppose that ∑i=1q⌊∣V(Hi)∣2⌋≤r\sum_{i=1}^{q}\left\lfloor\frac{|V(H_i)|}{2}\right\rfloor\leq r. Then, for every j≥2j\geq2,

kj(H)≤(2r+1j)(4)k_j(H)\leq\binom{2r+1}{j} \tag*{(4)}

If 2≤j≤2r+12\leq j\leq2r+1, equality holds if and only if H=K2r+1H=K_{2r+1}, up to isolated vertices.

Proof. We can ignore isolated vertices in HH. Put ri=⌊∣V(Hi)∣/2⌋r_i=\lfloor|V(H_i)|/2\rfloor for each remaining component, and let R=∑iri≤rR=\sum_i r_i\leq r. Each component has at most 2ri+12r_i+1 vertices. Now take complete graphs of orders 2ri+12r_i+1 and identify one vertex of each with a single common vertex zz, keeping all other vertices distinct. The resulting graph JJ has 2R+12R+1 vertices, and every clique of order at least two lies within one of these complete graphs. Therefore

kj(H)≤∑i(2ri+1j)=kj(J)≤(2R+1j)≤(2r+1j).k_j(H)\leq\sum_i\binom{2r_i+1}{j}=k_j(J)\leq\binom{2R+1}{j}\leq\binom{2r+1}{j}.

Suppose that 2≤j≤2r+12\leq j\leq2r+1 and equality holds in (4) and thus in the above chain as well. Since the right-hand side is positive we get R=rR=r. Equality kj(J)=(2r+1j)k_j(J)=\binom{2r+1}{j} forces JJ to be complete. If there are at least two nontrivial components in HH, then we will get two vertices in JJ each corresponding to one of these components, which will be non-adjacent, resulting in a contradiction. Hence there is only one nontrivial component of HH. That component must have 2r+12r+1 vertices, and all its jj-sets must be cliques, so it is K2r+1K_{2r+1}. The converse is easy to check.

Let o(X)o(X) denote the number of odd components in XX. The Tutte-Berge formula states that

ν(G)=12min⁡S⊆V(G)(∣V(G)∣+∣S∣−o(G−S)).\nu(G)=\frac{1}{2}\min_{S\subseteq V(G)}\left(|V(G)|+|S|-o(G-S)\right).

Let C(X)\mathcal{C}(X) denote the set of all the components of XX. The Tutte-Berge formula is equivalent to

ν(G)=min⁡S⊆V(G)(∣S∣+∑C∈C(G−S)⌈∣V(C)∣2⌉).(5)\nu(G)=\min_{S\subseteq V(G)}\left(|S|+\sum_{C\in\mathcal{C}(G-S)}\left\lceil\frac{|V(C)|}{2}\right\rceil\right). \tag*{(5)}

Let C1,C2,…,CkC_1,C_2,\ldots,C_k be the odd components of G−SG-S and Ck+1,…,ClC_{k+1},\ldots,C_l be the even ones. Let ⌈∣V(Ci)∣2⌉=ri\left\lceil\frac{|V(C_i)|}{2}\right\rceil=r_i for all i∈[l]i\in[l]. Since ∣V(G)∣−∣S∣=2∑i=1lri+k|V(G)|-|S|=2\sum_{i=1}^{l}r_i+k and o(G−S)=ko(G-S)=k, we have

∣V(G)∣+∣S∣−o(G−S)2=∣S∣+∣V(G)∣−∣S∣−o(G−S)2=∣S∣+2∑i=1lri+k−k2=∣S∣+∑i=1lri.\begin{aligned} \frac{|V(G)|+|S|-o(G-S)}{2}=|S|+\frac{|V(G)|-|S|-o(G-S)}{2} \\ &=|S|+\frac{2\sum_{i=1}^{l}r_i+k-k}{2}=|S|+\sum_{i=1}^{l}r_i. \end{aligned}

Proof of Theorem 2.1. Let GG satisfy Δ(G)≤D\Delta(G)\le D, ν(G)≤M\nu(G)\le M and D≥2MD\ge2M, and choose SS to be a Tutte-Berge set for GG, that is, a set attaining the minimum in (5). Put s=∣S∣s=|S|. Then from (5),

0≤s≤M,∑C∈C(G−S)⌈∣V(C)∣2⌉≤M−s.(6)0\le s\le M,\qquad\sum_{C\in\mathcal{C}(G-S)}\left\lceil\frac{|V(C)|}{2}\right\rceil\le M-s. \tag*{(6)}

Fix 3≤t≤2M+13\le t\le2M+1. The cliques with at most one vertex outside SS are bounded by Lemma 2.3. From (6), D≥2M≥2sD\ge2M\ge2s. If a clique uses j≥2j\ge2 vertices outside SS, those vertices lie in a single component of G−SG-S and those vertices form a jj-clique. There are at most (st−j)\binom{s}{t-j} choices for its vertices in SS. Using Lemmas 2.3 and 2.4, (6), and Vandermonde’s identity, we get

kt(G)=ct(G,S,≤1)+ct(G,S,≥2)≤(st)+(D+1−s)(st−1)+∑j=2t(st−j)(2(M−s)+1j)=(2M+1−st)+(D−2M+s)(st−1).(7)\begin{aligned} k_t(G)=c_t(G,S,\le1)+c_t(G,S,\ge2)\le\binom{s}{t}+(D+1-s)\binom{s}{t-1}+\sum_{j=2}^{t}\binom{s}{t-j}\binom{2(M-s)+1}{j} \\ &=\binom{2M+1-s}{t}+(D-2M+s)\binom{s}{t-1}. \tag*{(7)} \end{aligned}

Put

Ht(s)=(2M+1−st)+(D−2M+s)(st−1).H_t(s)=\binom{2M+1-s}{t}+(D-2M+s)\binom{s}{t-1}.

We now aim to maximize Ht(s)H_t(s) for integers 0≤s≤M0\le s\le M. For 0≤s≤M−20\le s\le M-2, Pascal’s identity gives

Δ2Ht(s)=Ht(s+2)−2Ht(s+1)+Ht(s)=(2M−1−st−2)+(D−2M+s+2)(st−3)+2(st−2)≥0.(8)\begin{aligned} \Delta^2H_t(s)=H_t(s+2)-2H_t(s+1)+H_t(s) \\ &=\binom{2M-1-s}{t-2}+(D-2M+s+2)\binom{s}{t-3}+2\binom{s}{t-2}\ge0. \tag*{(8)} \end{aligned}

Since D≥2MD\ge2M, Δ2Ht(s)\Delta^2H_t(s) is nonnegative and thus HtH_t is a convex sequence. Its endpoint values are Ht(0)=At(M)H_t(0)=A_t(M) and Ht(M)=Bt(D,M)H_t(M)=B_t(D,M), so

kt(G)≤Ht(s)≤(1−sM)At(M)+sMBt(D,M)≤max⁡{At(M),Bt(D,M)}.(9)k_t(G)\le H_t(s)\le\left(1-\frac{s}{M}\right)A_t(M)+\frac{s}{M}B_t(D,M)\le\max\{A_t(M),B_t(D,M)\}. \tag*{(9)}

For M≥2M \ge2, the second forward difference at s=0s = 0 satisfies

Δ2Ht(0)≥(2M−1t−2)>0.\Delta^{2} H_t(0) \ge\binom{2M - 1}{t - 2} > 0.

Thus, the forward differences are nondecreasing and not all equal. Consequently, the average of any proper initial segment of the forward differences is strictly smaller than their overall average. This implies that Ht(s)H_t(s) lies strictly below the line segment joining its endpoint values Ht(0)H_t(0) and Ht(M)H_t(M) at every integer 0<s<M0 < s < M. Hence, the middle inequality in (9) is strict whenever 0<s<M0 < s < M. For M=1M = 1, there are no interior integers, so the assertion is vacuously true.

Both endpoint constructions are feasible and attain the corresponding counts in (1), proving (2). Now suppose GG attains the maximum. (9) and the analysis above imply that s=0s = 0 or s=Ms = M.

If s=0s = 0, the bound on the component orders in (6) and equality in Lemma 2.4 imply that G=K2M+1G = K_{2M+1} apart from isolated vertices. Clearly, this case is possible only when At(M)≥Bt(D,M)A_t(M) \ge B_t(D, M).

If s=Ms = M, from (6), every component of G−SG - S has order one, so SS is a vertex cover. The equality value Bt(D,M)B_t(D, M) must be positive, which implies t−1≤Mt - 1 \le M. Thus, we can apply the equality condition from Lemma 2.3. Equality in Lemma 2.3 forces G[S]=KMG[S] = K_M and every vertex of SS to have degree DD. Moreover, all vertices outside SS with a neighbour in SS have the same neighbourhood SS. Therefore, there are exactly D+1−MD + 1 - M of these vertices and all the other vertices outside SS are isolated. Thus G=SD,MG = S_{D,M} apart from isolated vertices. This case is possible only when Bt(D,M)≥At(M)B_t(D, M) \ge A_t(M).

The boundary case D=2M−1D = 2M - 1

In the previous section, we studied the clique bound Ft(D,M)F_t(D, M) when D≥2MD \ge2M. Here we will study what happens for the boundary case of D=2M−1D = 2M - 1. It is easy to check that t>2Mt > 2M is not interesting, since a clique with order more than 2M2M contains vertices of degree at least 2M2M.

Theorem 3.1. For M≥2M \ge2 and 3≤t≤2M3 \le t \le2M,

Ft(2M−1,M)=(2Mt).F_t(2M - 1, M) = \binom{2M}{t}.

K2MK_{2M} is the unique extremal graph, up to isolated vertices. For t>2Mt > 2M the maximum is zero.

For a vertex vv in GG, let TvT_v denote the set of tt-cliques meeting N[v]N[v]. Chao and Dong [2 Lemma 2] proved that for t≥3t \ge3,

∑v∈V(G)∣Tv∣≤∑v∈V(G)(dG(v)+1t).(10)\sum_{v \in V(G)} |T_v| \le\sum_{v \in V(G)} \binom{d_G(v) + 1}{t}. \tag*{(10)}

We now establish a lemma as a consequence of the above bound.

Lemma 3.2. Let M≥2M \ge2 and 3≤t≤2M3 \le t \le2M. If ∣V(G)∣≤2M+1|V(G)| \le2M + 1 and Δ(G)≤2M−1\Delta(G) \le2M - 1, then kt(G)≤(2Mt)k_t(G) \le\binom{2M}{t}. Equality holds only for K2MK_{2M}, with possibly one isolated vertex.

Proof. It is easy to check that the result holds when ∣V(G)∣≤2M|V(G)| \le2M, or when GG has an isolated vertex. Suppose that ∣V(G)∣=2M+1|V(G)| = 2M + 1 and that GG has no isolated vertex. Suppose for a contradiction that kt(G)≥(2Mt)k_t(G) \ge\binom{2M}{t}. For a vertex vv of degree dd, at most (2M−dt)\binom{2M-d}{t} cliques do not intersect with N[v]N[v],

∣Tv∣≥(2Mt)−(2M−dt).|T_v| \ge\binom{2M}{t} - \binom{2M-d}{t}.

If 1≤d≤2M−21 \le d \le2M-2, convexity of the binomial coefficients gives

(d+1t)+(2M−dt)≤(2M−1t)+(2t)<(2Mt).\binom{d+1}{t}+\binom{2M-d}{t}\le\binom{2M-1}{t}+\binom{2}{t}<\binom{2M}{t}.

Therefore, ∣Tv∣>(d+1t)|T_v|>\binom{d+1}{t} whenever 1≤d≤2M−21\le d\le2M-2. If d=2M−1d=2M-1, we instead get ∣Tv∣≥(2Mt)−(1t)=(d+1t)|T_v|\ge\binom{2M}{t}-\binom{1}{t}=\binom{d+1}{t}. Since we assumed GG has no isolated vertex, every vertex has degree at least one. Moreover, by the handshaking lemma, not all 2M+12M+1 vertices can have degree 2M−12M-1. Thus, at least one vertex has degree at most 2M−22M-2. Therefore, summing these inequalities over V(G)V(G) contradicts (10). Hence, kt(G)<(2Mt)k_t(G)<\binom{2M}{t} when ∣V(G)∣=2M+1|V(G)|=2M+1 and GG has no isolated vertex.

We now use Lemma 3.2 to obtain the desired bound and extremal graph for D=2M−1D=2M-1.

Proof of Theorem 3.1. Let D=2M−1D=2M-1 and let GG be feasible. We will look into two cases.

Case 1. There exists a vertex v∈V(G)v\in V(G) such that ν(G−v)<ν(G)\nu(G-v)<\nu(G). Since ν(G)≤M\nu(G)\le M, we have ν(G−v)≤M−1\nu(G-v)\le M-1. Also, Δ(G−v)≤2M−1\Delta(G-v)\le2M-1. We first show that

kt(G−v)≤(2M−1t).(11)k_t(G-v)\le\binom{2M-1}{t}. \tag*{(11)}

Suppose first that 3≤t≤2M−13\le t\le2M-1. We may apply Theorem 2.1 to G−vG-v with matching bound M−1M-1 and degree bound D=2M−1D=2M-1. Writing r=M−1r=M-1, we obtain

kt(G−v)≤max⁡{(2r+1t),(rt)+(r+2)(rt−1)}.k_t(G-v)\le\max\left\{\binom{2r+1}{t},\binom{r}{t}+(r+2)\binom{r}{t-1}\right\}.

We claim that the first term is at least the second. For 3≤t≤r+13\le t\le r+1, Vandermonde’s identity gives

(2r+1t)=∑i=0t(r+1i)(rt−i)≥(rt)+(r+1)(rt−1)+(r+12)(rt−2)>(rt)+(r+2)(rt−1),\binom{2r+1}{t}=\sum_{i=0}^{t}\binom{r+1}{i}\binom{r}{t-i}\ge\binom{r}{t}+(r+1)\binom{r}{t-1}+\binom{r+1}{2}\binom{r}{t-2}>\binom{r}{t}+(r+2)\binom{r}{t-1},

where the last strict inequality follows from (r+12)(rt−2)>(rt−1)\binom{r+1}{2}\binom{r}{t-2}>\binom{r}{t-1}. For t>r+1t>r+1, both terms in the second expression become zero, so the claimed comparison follows. This proves (11) for 3≤t≤2M−13\le t\le2M-1, and it is easy to check for t≥2Mt\ge2M.

Since D=2M−1D=2M-1, we have ∣N(v)∣≤2M−1|N(v)|\le2M-1. The tt-cliques in GG can be partitioned based on whether they contain vv. The number of tt-cliques containing vv is therefore at most (2M−1t−1)\binom{2M-1}{t-1}. By (11), the number of tt-cliques not containing vv is at most (2M−1t)\binom{2M-1}{t}. Thus,

kt(G)≤(2M−1t)+(2M−1t−1)=(2Mt).k_t(G)\le\binom{2M-1}{t}+\binom{2M-1}{t-1}=\binom{2M}{t}.

Suppose kt(G)=(2Mt)k_t(G)=\binom{2M}{t}. Therefore, kt−1(G[N(v)])=(2M−1t−1)k_{t-1}(G[N(v)])=\binom{2M-1}{t-1}. Since 2≤t−1≤2M−12\le t-1\le2M-1 and d(v)≤2M−1d(v)\le2M-1, this forces d(v)=2M−1d(v)=2M-1 and G[N(v)]=K2M−1G[N(v)]=K_{2M-1}. Thus, G[N[v]]=K2MG[N[v]]=K_{2M}. Every vertex of this K2MK_{2M} already has degree 2M−12M-1, so the degree bound Δ(G)≤2M−1\Delta(G)\le2M-1 implies that this clique is a connected component of GG. Moreover, it contains a matching of size MM, thus it uses up the entire matching budget. Hence no other component can contain an edge. Thus all vertices outside this component are isolated.

Case 2. ν(G−v)=ν(G)\nu(G-v)=\nu(G) for every vertex v∈V(G)v\in V(G). Gallai’s lemma, in the form used by Balachandran and Khare [1 Theorem 3], says that every nontrivial component CiC_i is factor-critical and has 2ri+12r_i+1 vertices, where ri=ν(Ci)≥1r_i=\nu(C_i)\ge1. Let R=∑iri≤MR=\sum_i r_i \le M. If there is at most one nontrivial component, then, after removing isolated vertices, GG has at most 2M+12M+1 vertices. Therefore Lemma 3.2 gives kt(G)≤(2M+1t)k_t(G) \le\binom{2M+1}{t}. Equality would require G=K2MG=K_{2M}, possibly with one isolated vertex, which is impossible since every nontrivial factor-critical component has odd order.

Now suppose that there are at least two nontrivial components. Let CC be one such component and ν(C)=x\nu(C)=x, where 1≤x≤R−11\le x\le R-1. By applying Lemma 2.4 to G∖CG\setminus C and using convexity, we get

kt(G)=kt(G∖C)+kt(C)≤(2(R−x)+1t)+(2x+1t)≤(2R−1t)+(3t)≤(2M−1t)+(3t)<(2Mt).\begin{aligned} k_t(G) &= k_t(G\setminus C)+k_t(C) \\ &\le\binom{2(R-x)+1}{t}+\binom{2x+1}{t}\\ &\le\binom{2R-1}{t}+\binom{3}{t} \le\binom{2M-1}{t}+\binom{3}{t} <\binom{2M}{t}. \end{aligned}

The final strict inequality follows from Pascal’s identity and (2M−1t−1)>(3t)\binom{2M-1}{t-1}>\binom{3}{t} for 3≤t≤2M3\le t\le2M. Since the inequality is strict in Case 2, the only extremal graph comes from Case 1, which is K2MK_{2M} with possible isolated vertices.

Conversely, K2MK_{2M} has maximum degree 2M−12M-1, matching number MM, and exactly (2Mt)\binom{2M}{t} copies of KtK_t.

Generic upper bound and improvement when D is even

The previous sections determine Ft(D,M)F_t(D,M) when D≥2M−1D\ge2M-1. We now give an upper bound valid for all degree and matching bounds, and then improve it when DD is even. The argument also gives information about the structure of the extremal graphs.

Chvátal and Hanson [3] proved that, for D≥1D\ge1 and M≥0M\ge0,

F2(D,M)=DM+⌊D2⌋⌊M⌊D/2⌋⌋.(12)F_2(D,M)=DM+\left\lfloor\frac{D}{2}\right\rfloor\left\lfloor\frac{M}{\lfloor D/2\rfloor}\right\rfloor. \tag*{(12)}

We first use this result to bound the number of larger cliques.

Theorem 4.1. Let D≥1D\ge1, M≥0M\ge0, and 2≤t≤D+12\le t\le D+1 be integers. Every graph GG with Δ(G)≤D\Delta(G)\le D and ν(G)≤M\nu(G)\le M satisfies

kt(G)≤Ut(D,M)=(D−1t−2)(t2)(DM+⌊D2⌋⌊M⌊D/2⌋⌋).(13)k_t(G)\le U_t(D,M)=\frac{\binom{D-1}{t-2}}{\binom{t}{2}}\left(DM+\left\lfloor\frac{D}{2}\right\rfloor\left\lfloor\frac{M}{\lfloor D/2\rfloor}\right\rfloor\right). \tag*{(13)}

Therefore, Ft(D,M)≤⌊Ut(D,M)⌋F_t(D,M)\le\lfloor U_t(D,M)\rfloor.

Proof. Fix an edge uv∈E(G)uv\in E(G). Every tt-clique containing uvuv is obtained by choosing a (t−2)(t-2)-clique in N(u)∩N(v)N(u)\cap N(v). Since ∣N(u)∩N(v)∣≤D−1|N(u)\cap N(v)|\le D-1, the edge uvuv lies in at most (D−1t−2)\binom{D-1}{t-2} copies of KtK_t. Counting the pairs consisting of a tt-clique and one of its edges gives

(t2)kt(G)≤(D−1t−2)∣E(G)∣≤(D−1t−2)F2(D,M),\binom{t}{2}k_t(G)\le\binom{D-1}{t-2}|E(G)|\le\binom{D-1}{t-2}F_2(D,M),

where the last inequality follows from (12). Dividing by (t2)\binom{t}{2} proves (13). Since kt(G)k_t(G) is an integer, the bound for Ft(D,M)F_t(D,M) also follows.

Putting t=2t=2 in (13) gives exactly (12). For t≥3t\ge3, the bound need not be sharp, since an edge need not lie in all (D−1t−2)\binom{D-1}{t-2} possible copies of KtK_t. We will now keep track of some of this loss.

For D≥2D \ge2 and 3≤t≤D+13 \le t \le D+1, put

a=(D−1t−2),b=(t2),c=(D−2t−3).(14)a=\binom{D-1}{t-2},\qquad b=\binom{t}{2},\qquad c=\binom{D-2}{t-3}. \tag*{(14)}

Note that a,b,c>0a,b,c>0 throughout this range.

Lemma 4.2. Let Δ(G)≤D\Delta(G)\le D, where D≥2D\ge2, and let 3≤t≤D+13\le t\le D+1. Obtain HH from GG by deleting all components isomorphic to KD+1K_{D+1} and all isolated vertices. Then

bk⁡t(G)≤a∣E(G)∣−c2∣V(H)∣.(15)\operatorname{bk}_t(G)\le a|E(G)|-\frac{c}{2}|V(H)|. \tag*{(15)}

Proof. Call an edge uvuv deficient if ∣N(u)∩N(v)∣≤D−2|N(u)\cap N(v)|\le D-2, and let BB be the set of all deficient edges. Every edge lies in at most aa copies of KtK_t, whereas a deficient edge lies in at most

(D−2t−2)=a−c\binom{D-2}{t-2}=a-c

such copies. Therefore, counting the number of tt-cliques containing each edge gives

bk⁡t(G)≤a∣E(G)∣−c∣B∣.\operatorname{bk}_t(G)\le a|E(G)|-c|B|.

We claim that every vertex of HH is incident with a deficient edge. Let v∈V(H)v\in V(H). If dG(v)<Dd_G(v)<D, then every edge incident with vv is deficient. Suppose instead that dG(v)=Dd_G(v)=D and no edge incident with vv is deficient. For each u∈N(v)u\in N(v), this gives ∣N(u)∩N(v)∣=D−1|N(u)\cap N(v)|=D-1, so uu is adjacent to every vertex of N(v)∖{u}N(v)\setminus\{u\}. Thus G[N[v]]=KD+1G[N[v]]=K_{D+1}. Every vertex of this clique already has degree DD, so it is a component of GG. This contradicts the choice of HH.

Since HH has no isolated vertices, the claim gives 2∣B∣≥∣V(H)∣2|B|\ge|V(H)|. Substituting this into the preceding inequality proves (15). □

Notice that Lemma 4.2 does not require DD to be even. Let D=2hD=2h, write M=qh+rM=qh+r, where 0≤r<h0\le r<h, and put A=(D+1t)A=\binom{D+1}{t}. Define f0=0f_0=0 and

fr=max⁡{(2r+1t),(rt)+(D+1−r)(rt−1)}(1≤r<h).(16)f_r=\max\left\{\binom{2r+1}{t},\binom{r}{t}+(D+1-r)\binom{r}{t-1}\right\}\qquad(1\le r<h). \tag*{(16)}

These two expressions are the clique counts of the complete and complete split constructions introduced earlier, respectively. We write qKD+1qK_{D+1} for the disjoint union of qq copies of KD+1K_{D+1}.

Theorem 4.3. Let D=2h≥2D=2h\ge2, 3≤t≤D+13\le t\le D+1, and M≥0M\ge0 be integers. Write M=qh+rM=qh+r, where 0≤r<h0\le r<h. Then

qA+fr≤Ft(D,M)≤qA+⌊(Da−c)rb⌋.(17)qA+f_r\le F_t(D,M)\le qA+\left\lfloor\frac{(Da-c)r}{b}\right\rfloor. \tag*{(17)}

Proof. For r>0r>0, let JrJ_r be whichever of K2r+1K_{2r+1} and SD,rS_{D,r} has more tt-cliques, and let J0J_0 be the empty graph. Since r<hr<h, we have Δ(Jr)≤D\Delta(J_r)\le D and ν(Jr)≤r\nu(J_r)\le r. Thus qKD+1∪˙JrqK_{D+1}\mathbin{\dot\cup}J_r is feasible and has qA+frqA+f_r copies of KtK_t, proving the lower bound.

For the upper bound, let GG be feasible. We may assume that ν(G)=M\nu(G)=M, otherwise, add M−ν(G)M-\nu(G) disjoint copies of K2K_2. Since D≥2D\ge2 and t≥3t\ge3, this does not change bk⁡t(G)\operatorname{bk}_t(G) or violate the degree bound. Let pp be the number of components of GG isomorphic to KD+1K_{D+1}, and obtain HH by deleting these components and all isolated vertices. Each deleted KD+1K_{D+1}-component has matching number hh, so p≤qp \le q and ν(H)=M−ph=(q−p)h+r≥r\nu(H) = M - ph = (q-p)h + r \ge r. Therefore, ∣V(H)∣≥2r|V(H)| \ge2r. Also, (12) gives

∣E(G)∣≤DM+h⌊Mh⌋=D(qh+r)+hq=qh(D+1)+Dr.(18)|E(G)| \le DM + h\left\lfloor\frac{M}{h} \right\rfloor= D(qh+r)+hq = qh(D+1)+Dr. \tag*{(18)}

Since bA=ah(D+1)bA = ah(D+1), Lemma 4.2 gives

bkt(G)≤a∣E(G)∣−c2∣V(H)∣≤a(qh(D+1)+Dr)−cr=bqA+(Da−c)r.bk_t(G) \le a|E(G)|-\frac{c}{2}|V(H)| \le a\bigl(qh(D+1)+Dr\bigr)-cr = bqA+(Da-c)r.

Dividing by bb and using integrality proves the upper bound.

For the same parameters as above, Theorem 4.1 gives

Ft(D,M)≤qA+⌊Darb⌋.F_t(D,M) \le qA+\left\lfloor\frac{Dar}{b} \right\rfloor.

Thus (17) subtracts cr/bcr/b from the remainder term before rounding. This is a strict improvement of the unrounded estimate when r>0r>0, although the rounded bounds can coincide. When r=0r=0, both bounds are attained by qKD+1qK_{D+1}.

We now use the same argument to describe every extremal graph when DD is even.

Theorem 4.4. Let D=2h≥2D=2h\ge2, 3≤t≤D+13\le t\le D+1, and M≥0M\ge0 be integers, and put r=M mod hr=M\bmod h. Every graph attaining Ft(D,M)F_t(D,M), after its isolated vertices are deleted, has the form

G=pKD+1∪˙H,(19)G=pK_{D+1}\mathbin{\dot\cup} H, \tag*{(19)}

where HH has no KD+1K_{D+1}-component and is extremal for Ft(D,M−ph)F_t(D,M-ph). Moreover,

0≤M−ph≤⌊Dar−bfrc⌋,∣V(H)∣≤⌊2(Dar−bfr)c⌋.(20)0\le M-ph\le\left\lfloor\frac{Dar-bf_r}{c}\right\rfloor,\qquad|V(H)|\le\left\lfloor\frac{2(Dar-bf_r)}{c}\right\rfloor. \tag*{(20)}

Therefore, if M=qhM=qh, then

Ft(D,M)=q(D+1t),(21)F_t(D,M)=q\binom{D+1}{t}, \tag*{(21)}

and qKD+1qK_{D+1} is the unique extremal graph, up to isolated vertices.

Proof. Write M=qh+rM=qh+r, where 0≤r<h0\le r<h, and let GG be extremal. Delete all its pp components isomorphic to KD+1K_{D+1} and all isolated vertices to obtain HH. Since Δ(G)≤D\Delta(G)\le D, every copy of KD+1K_{D+1} must be a connected component of GG, as each of its vertices already has DD neighbours within the clique and hence cannot have any neighbour outside it. Thus, G=pKD+1∪˙HG=pK_{D+1}\mathbin{\dot\cup}H, up to isolated vertices, and HH has no KD+1K_{D+1}-component. By Theorem 4.3, kt(G)≥qA+frk_t(G)\ge qA+f_r. Combining Lemma 4.2 with (18) gives

c2∣V(H)∣≤a∣E(G)∣−bkt(G)≤a(qh(D+1)+Dr)−b(qA+fr)=Dar−bfr.(22)\frac{c}{2}|V(H)|\le a|E(G)|-bk_t(G)\le a\bigl(qh(D+1)+Dr\bigr)-b(qA+f_r)=Dar-bf_r. \tag*{(22)}

This proves ∣V(H)∣≤⌊2(Dar−bfr)c⌋|V(H)|\le\left\lfloor\frac{2(Dar-bf_r)}{c}\right\rfloor. Since ν(H)≤M−ph\nu(H)\le M-ph, the graph HH is feasible for Ft(D,M−ph)F_t(D,M-ph). If it were not extremal for this remaining matching bound, replacing it by a better feasible graph would increase kt(G)k_t(G) without violating either constraint. Thus HH is extremal for Ft(D,M−ph)F_t(D,M-ph). It remains to bound M−phM-ph. The inequality ph≤ν(G)≤Mph \le\nu(G) \le M gives M−ph≥0M-ph \ge0. To obtain the upper bound even when ν(G)<M\nu(G)<M, add M−ν(G)M-\nu(G) disjoint copies of K2K_2 to GG, and denote the resulting graph by G+G^{+}. This graph is still feasible and extremal, has matching number MM, and has the same pp components isomorphic to KD+1K_{D+1}. Its remainder H+H^{+} therefore has matching number M−phM-ph. Applying the order bound already proved in (22) to G+G^{+} gives

2(M−ph)≤∣V(H+)∣≤2(Dar−bfr)c.2(M-ph) \le|V(H^{+})| \le\frac{2(Dar-bf_r)}{c}.

Hence M−ph≤⌊Dar−bfrc⌋M-ph \le\left\lfloor\frac{Dar-bf_r}{c} \right\rfloor, proving (20).

Finally, if r=0r=0, then f0=Dar−bfrc=0f_0=\frac{Dar-bf_r}{c}=0. Thus HH is empty and M−ph=0M-ph=0, so p=qp=q. The graph qKD+1qK_{D+1} attains (21), proving the uniqueness assertion.

Corollary 4.5. Let D=2h≥2D=2h\ge2, 3≤t≤D+13\le t\le D+1, and M≥hM\ge h be integers, and put r=Mmod⁡hr=M\mathbin{\operatorname{mod}} h. If M>⌊Dar−bfrc⌋M>\left\lfloor\frac{Dar-bf_r}{c}\right\rfloor, then

Ft(D,M)=(D+1t)+Ft(D,M−h).(23)F_t(D,M)=\binom{D+1}{t}+F_t(D,M-h). \tag*{(23)}

Moreover, up to isolated vertices, the extremal graphs for Ft(D,M)F_t(D,M) are exactly the graphs

G=KD+1∪˙G′,G=K_{D+1}\mathbin{\dot\cup}G',

where G′G' is extremal for Ft(D,M−h)F_t(D,M-h).

Consequently, for fixed DD and tt, determining Ft(D,M)F_t(D,M) and its extremal graphs for all MM reduces to determining them for finitely many values of MM.

Proof. Let GG be extremal for Ft(D,M)F_t(D,M), and let pp be its number of components isomorphic to KD+1K_{D+1}. By Theorem 4.4,

M−ph≤⌊Dar−bfrc⌋<M.M-ph\le\left\lfloor\frac{Dar-bf_r}{c}\right\rfloor<M.

Therefore p≥1p\ge1, so GG contains a KD+1K_{D+1}-component. Delete one such component to obtain G′G'. Since ν(KD+1)=h\nu(K_{D+1})=h and matching number is additive over components, we have

Δ(G′)≤D,ν(G′)=ν(G)−h≤M−h.\Delta(G')\le D,\qquad\nu(G')=\nu(G)-h\le M-h.

Thus G′G' is feasible for Ft(D,M−h)F_t(D,M-h), giving

Ft(D,M)=kt(G)=(D+1t)+kt(G′)≤(D+1t)+Ft(D,M−h).F_t(D,M)=k_t(G)=\binom{D+1}{t}+k_t(G')\le\binom{D+1}{t}+F_t(D,M-h).

Conversely, adjoining a disjoint copy of KD+1K_{D+1} to any extremal graph for Ft(D,M−h)F_t(D,M-h) gives a graph with maximum degree at most DD, matching number at most MM, and exactly (D+1t)+Ft(D,M−h)\binom{D+1}{t}+F_t(D,M-h) copies of KtK_t. This proves (23) and shows that every graph constructed in this way is extremal.

For the graph G′G' obtained by deleting a KD+1K_{D+1}-component from an extremal graph GG, the recurrence gives

kt(G′)=Ft(D,M)−(D+1t)=Ft(D,M−h).k_t(G')=F_t(D,M)-\binom{D+1}{t}=F_t(D,M-h).

Hence G′G' must itself be extremal, proving the claimed characterization.

Finally, for fixed DD and tt, the threshold ⌊(Dar−bfr)/c⌋\left\lfloor(Dar-bf_r)/c\right\rfloor depends only on the remainder rr. Subtracting hh preserves this remainder. Therefore, we may apply the recurrence and the extremal characterization repeatedly until the remaining matching bound is at most this threshold or is less than hh. Since rr has only finitely many possible values, only finitely many matching bounds remain to be considered.

References

  1. [1]Niranjan Balachandran and Niraj Khare. Graphs with restricted valency and matching number. Discrete Mathematics, 309(12):4176–4180, 2009.DOI
  2. [2]Ting-Wei Chao and Zichao Dong. A simple proof of the Gan-Loh-Sudakov conjecture. The Electronic Journal of Combinatorics, 29(3):P3.59, 2022.DOI
  3. [3]Vašek Chvátal and Denis Hanson. Degrees and matchings. Journal of Combinatorial Theory, Series B, 20(2):128–138, 1976.DOI
  4. [4]Jian Wang. The shifting method and generalized Turán number of matchings. European Journal of Combinatorics, 85:103057, 2020.DOI

Paper details

vlnc:W_yjfhezxe
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents