betaFeedback

WorksMathematics

The size and structure of graphs with a unique kk-factor

Abstract

For integers n>k≥1n>k\ge1 with nknk even, let m(n,k)m(n,k) be the maximum size of a graph of order nn with a unique kk-factor. In 1964, Hetyei and in 1984, Hendry [J. Combin. Theory Ser. B 37 (1984), 53–63] proved m(n,1)=n2/4m(n,1)=n^2/4 for even nn and m(n,2)=⌊n(n+1)/4⌋m(n,2)=\lfloor n(n+1)/4\rfloor, respectively. In 2000, Johann [J. Graph Theory 35 (2000), 227–243] showed that m(n,k)=nk/2+(n−k2)m(n,k)=nk/2+\binom{n-k}{2} for k>n/2k>n/2 and knkn even and m(n,k)=n2/4+(k−1)n/4m(n,k)=n^2/4+(k-1)n/4 for n=2kqn=2kq, where qq is a positive integer. Later, Volkmann [Combinatorica 24 (2004), 531–540] proved m(n,k)=k2+(n−k2)m(n,k)=k^2+\binom{n-k}{2} for n/3≤k<n/2n/3\le k<n/2 and knkn even, and he determined m(n,3)m(n,3). In this paper, we determine m(n,k)m(n,k) for all admissible pairs, proving the size conjecture posed by Volkmann. We also prove that every extremal graph with 2≤k≤n−22\le k\le n-2 has a universal vertex whose neighbors in the unique factor are precisely its degree-kk vertices. In particular, this result confirms Volkmann's structural conjecture.

Introduction

Throughout this paper, we consider finite, undirected, simple graphs. The order and size of a graph GG are ∣V(G)∣|V(G)| and ∣E(G)∣|E(G)|, respectively. For x∈V(G)x \in V(G), let dG(x)d_G(x) denote its degree. For X⊆V(G)X \subseteq V(G), let G[X]G[X] be the induced subgraph; for disjoint X,Y⊆V(G)X,Y \subseteq V(G), let eG(X,Y)e_G(X,Y) count the edges between them. Write eG(X)=∣E(G[X])∣e_G(X)=|E(G[X])|. A vertex adjacent to every other vertex is universal. We denote by KnK_n the complete graph of order nn, by Kp,qK_{p,q} the complete bipartite graph with partite sets of sizes pp and qq, and by G‾\overline{G} the complement of GG. For disjoint graphs GG and HH, their join G+HG+H is obtained from their disjoint union by adding all edges between V(G)V(G) and V(H)V(H).

For a function f:V(G)→Z≥0f: V(G) \to\mathbb{Z}_{\ge0}, an ff-factor is a spanning subgraph FF satisfying dF(x)=f(x)d_F(x)=f(x) for every x∈V(G)x \in V(G). If f(x)=kf(x)=k for every vertex x∈V(G)x \in V(G), then FF is called a kk-factor. For integers n>k≥1n>k\ge1 with nknk even, define

m(n,k)=max⁡{∣E(G)∣:∣V(G)∣=n and G has a unique k-factor}.m(n,k)=\max\{|E(G)|: |V(G)|=n\text{ and }G\text{ has a unique }k\text{-factor}\}.

Whenever FF is the unique kk-factor, we color its edges red and the remaining edges of GG blue, and write Er=E(F)E_r=E(F) and Eb=E(G)∖E(F)E_b=E(G)\setminus E(F). We use Nr(x)N_r(x) and Nb(x)N_b(x) for the red and blue neighborhoods of the vertex x∈V(G)x \in V(G).

E-mail addresses: [email protected] (Z. Yang)

In 1964, Hetyei (see Corollary 1.6 in [9]) determined m(n,1)m(n,1), and in 1984, Hendry [2] determined m(n,2)m(n,2). In 2000, Johann [7] proved the general bound

m(n,k)≤n2+(k−1)n4,m(n,k) \le\frac{n^2+(k-1)n}{4},

with equality when nn is a multiple of 2k2k, and determined the maximum graphs when k>n/2k>n/2. Later, Volkmann [10] determined m(n,k)m(n,k) for 2k<n≤3k2k<n\le3k and for k=3k=3, and supplied constructions for all suitable positive integers nn and kk.

Let n=2kq+rn=2kq+r, q≥0q\ge0, and 0≤r<2k0\le r<2k, and define

ϑk(r):={r(k+1−r),0≤r≤k,(r−k−1)(2k−r),k+1≤r<2k.\vartheta_k(r):= \begin{cases} r(k+1-r), & 0\le r\le k,\\ (r-k-1)(2k-r), & k+1\le r<2k. \end{cases}

Define

h(n,k):=n2+(k−1)n−ϑk(r)4.h(n,k):=\frac{n^2+(k-1)n-\vartheta_k(r)}{4}.

Volkmann [10] conjectured that m(n,k)=h(n,k)m(n,k)=h(n,k) for all suitable positive integers nn and kk.

Conjecture 1.1 (Volkmann, [10]). For positive integers n>k≥2n>k\ge2 and nknk even, m(n,k)=h(n,k)m(n,k)=h(n,k).

Our first result proves Conjecture 1.1.

Theorem 1.2. Let n>k≥2n>k\ge2 be integers such that nknk is even. If n=2kq+rn=2kq+r with 0≤r<2k0\le r<2k, then

m(n,k)={n2+(k−1)n−r(k+1−r)4,for 0≤r≤k,n2+(k−1)n−(r−k−1)(2k−r)4,for k+1≤r<2k.m(n,k)= \begin{cases} \frac{n^2+(k-1)n-r(k+1-r)}{4}, & \text{for }0\le r\le k,\\ \frac{n^2+(k-1)n-(r-k-1)(2k-r)}{4}, & \text{for }k+1\le r<2k. \end{cases}

Remark. The previously determined cases include k=2,3k=2,3, the range n≤3kn\le3k, and the residue classes r=0,k+1r=0,k+1. Outside these ranges, the unresolved cases of the conjecture are contained in k≥4k\ge4, n>3kn>3k, and r∈{1,…,k}∪{k+2,…,2k−1}r\in\{1,\ldots,k\}\cup\{k+2,\ldots,2k-1\}, subject to nknk being even.

Hoffmann and Volkmann [3, 4] studied unique regular factors and saturated graphs with prescribed degrees in bipartite graphs. Hoffmann, Sidorowicz, and Volkmann [5] solved the extremal size problem in bipartite graphs and determined structural properties of its extremal graphs. Volkmann [10 Corollary 2.3] proved that a graph with a unique kk-factor, k≥2k\ge2, has minimum degree at most k+1k+1; see also Akbari, Ghodrati, and Hosseinzadeh [1 Corollary 1.5]. For a graph with a unique kk-factor, Volkmann [10] gave the following conjecture.

Conjecture 1.3 (Volkmann, [10]). Let GG be a graph of order nn with a unique kk-factor such that 2≤k≤n−22\le k\le n-2. If GG is of maximum size, then GG contains exactly kk vertices of degree kk.

Our second result shows the following stronger statement.

Theorem 1.4. Let 2≤k≤n−22\le k\le n-2, and let GG be a graph of order nn and size m(n,k)m(n,k) with unique kk-factor FF. Then D={v∈V(G):dG(v)=k}D=\{v\in V(G):d_G(v)=k\} has size kk. Moreover, GG has a universal vertex xx such that Nr(x)=DN_r(x)=D.

Some technical lemmas

The following theorem will be used when every prescribed degree is positive.

Theorem 2.1 (Jackson and Whitty, [6]). Let GG be a 22-edge-connected graph with a unique ff-factor, where f(v)>0f(v)>0 for every v∈V(G)v \in V(G). Then some vertex xx satisfies dG(x)=f(x)d_G(x)=f(x).

We recall the following necessary factor inequality, which is a corollary of Lovász’s (g,f)(g,f)-factor theorem [8] with g(v)=f(v)=b(v)g(v)=f(v)=b(v) for every vertex vv. For a function bb, write b(X)=∑x∈Xb(x)b(X)=\sum_{x\in X}b(x).

Proposition 2.2. Let HH be a graph with a bb-factor, where b:V(H)→Z≥0b:V(H)\to\mathbb{Z}_{\geq0}. If S,TS,T partition V(H)V(H), then

b(S)−b(T)+∑v∈TdH(v)−eH(S,T)≥0.b(S)-b(T)+\sum_{v\in T}d_H(v)-e_H(S,T)\geq0.

Fix a finite vertex set UU and f:U→Z≥0f:U\to\mathbb{Z}_{\geq0}. We call a graph RR on UU ff-extremal if it has a unique ff-factor and has maximum size among graphs on UU with a unique ff-factor. For X⊆UX\subseteq U, write f(X)=∑v∈Xf(v)f(X)=\sum_{v\in X}f(v). If LL is its unique factor, a vertex is free if f(v)=0f(v)=0, and tight if f(v)>0f(v)>0 and dR(v)=f(v)d_R(v)=f(v).

Lemma 2.3. Let RR be ff-extremal with unique ff-factor LL. Then the following two statements hold:

(i) if xx is free, then xx is universal, and R−xR-x is extremal for f∣U∖{x}f|_{U\setminus\{x\}};

(ii) if xx is tight, then every edge incident to xx belongs to LL, and R−xR-x is extremal for the function fx(y)=f(y)−1xy∈E(L)f_x(y)=f(y)-1_{xy\in E(L)} for every y∈U∖{x}y\in U\setminus\{x\}.

Proof. We prove the two statements separately.

(i) Let xx be a free vertex. Since f(x)=0f(x)=0, every ff-factor has degree 00 at xx. It follows that no edge incident to xx can be used in any ff-factor of RR.

We now show that xx is universal. Suppose, for contradiction, that xx is not universal. Then there exists some vertex y∈U∖{x}y\in U\setminus\{x\} with xy∉E(R)xy\notin E(R). Let R′=R+xyR'=R+xy. Since edges incident to xx cannot belong to any ff-factor, the set of ff-factors of R′R' is exactly the same as the set of ff-factors of RR. In particular, R′R' still has a unique ff-factor LL. However, ∣E(R′)∣=∣E(R)∣+1>∣E(R)∣|E(R')|=|E(R)|+1>|E(R)|, which contradicts the assumption that RR is ff-extremal. Hence xx is universal.

We next prove that R−xR-x is extremal for f∣U∖{x}f|_{U\setminus\{x\}}. Suppose, for contradiction, that R−xR-x is not extremal. Note that R−xR-x has a unique f∣U∖{x}f|_{U\setminus\{x\}}-factor, namely L−xL-x, since every such factor extends to an ff-factor of RR by adjoining xx as an isolated vertex. Thus there exists a graph R′′R'' on vertex set U∖{x}U\setminus\{x\} such that ∣E(R′′)∣>∣E(R−x)∣|E(R'')|>|E(R-x)| and R′′R'' has a unique f∣U∖{x}f|_{U\setminus\{x\}}-factor. Construct a new graph R′′′R''' on UU by adding the vertex xx to R′′R'' and joining xx to every vertex in U∖{x}U\setminus\{x\}. Since xx remains free, the ff-factors of R′′′R''' are in bijection with the f∣U∖{x}f|_{U\setminus\{x\}}-factors of R′′R'', so R′′′R''' has a unique ff-factor. Since xx is universal in RR, we have

∣E(R′′′)∣=∣E(R′′)∣+(∣U∣−1)>∣E(R−x)∣+(∣U∣−1)=∣E(R)∣,|E(R''')|=|E(R'')|+(|U|-1)>|E(R-x)|+(|U|-1)=|E(R)|,

contradicting the extremality of RR. Therefore R−xR-x must be f∣U∖{x}f|_{U\setminus\{x\}}-extremal.

::: (ii) Let xx be a tight vertex. Then f(x)>0f(x)>0 and dR(x)=f(x)d_R(x)=f(x). Note that every ff-factor of RR contains all edges incident to xx. Indeed, for any ff-factor FF, we have dF(x)=f(x)=dR(x)d_F(x)=f(x)=d_R(x). As FF is a spanning subgraph of RR, this equality forces FF to contain all edges incident to xx. Also, fx(y)≥0f_x(y)\geq0 for every y≠xy\ne x, since xy∈E(L)xy\in E(L) implies f(y)=dL(y)≥1f(y)=d_L(y)\geq1. We now establish a bijection between the set of ff-factors of RR and the set of fxf_x-factors of R−xR-x. Let FF be any ff-factor of RR. Since FF must contain all edges incident to xx, the subgraph F−xF-x satisfies

dF−x(y)=dF(y)−1xy∈E(F)=f(y)−1xy∈E(L)=fx(y)d_{F-x}(y)=d_F(y)-\mathbf{1}_{xy\in E(F)}=f(y)-\mathbf{1}_{xy\in E(L)}=f_x(y)

for all y≠xy\ne x. Hence F−xF-x is an fxf_x-factor of R−xR-x. Conversely, let F′F' be any fxf_x-factor of R−xR-x. Construct a spanning subgraph FF on UU by setting E(F)=E(F′)∪ER(x)E(F)=E(F')\cup E_R(x), where ER(x)E_R(x) is the set of edges incident to xx in RR. Then dF(x)=dR(x)=f(x)d_F(x)=d_R(x)=f(x) and

dF(y)=dF′(y)+1xy∈E(L)=fx(y)+1xy∈E(L)=f(y)d_F(y)=d_{F'}(y)+\mathbf{1}_{xy\in E(L)}=f_x(y)+\mathbf{1}_{xy\in E(L)}=f(y)

for all y≠xy\ne x, so FF is an ff-factor of RR. These two constructions are inverse to each other. Since RR has a unique ff-factor, it follows immediately that R−xR-x has a unique fxf_x-factor, namely L−xL-x.

It remains to show that R−xR-x is fxf_x-extremal. Suppose, for contradiction, that there exists a graph R′′R'' on U∖{x}U\setminus\{x\} with ∣E(R′′)∣>∣E(R−x)∣|E(R'')|>|E(R-x)| and a unique fxf_x-factor. Construct a new graph R′′′R''' on UU by adding the vertex xx to R′′R'', and joining xx exactly to its neighbors in LL. Since dR′′′(x)=f(x)d_{R'''}(x)=f(x), every ff-factor of R′′′R''' contains all edges incident to xx. Hence the same bijection argument shows that R′′′R''' has a unique ff-factor, and

∣E(R′′′)∣=∣E(R′′)∣+f(x)>∣E(R−x)∣+f(x)=∣E(R)∣,|E(R''')|=|E(R'')|+f(x)>|E(R-x)|+f(x)=|E(R)|,

which contradicts the extremality of RR. Hence R−xR-x is fxf_x-extremal. □

Theorem 2.4. Let RR be an ff-extremal graph of positive order with unique ff-factor LL. If f(v)>0f(v)>0 for every v∈V(R)v\in V(R), then RR has a tight vertex.

Proof. We use induction on ∣V(R)∣|V(R)|. For ∣V(R)∣=1|V(R)|=1, a graph of order one cannot admit an ff-factor with positive prescribed degree at its only vertex, so the initial case is vacuous. Assume that the result holds for all smaller orders. In the following, we will complete the proof by contradiction. Suppose that RR has no tight vertex.

Claim 1. RR is connected.

Proof of Claim 1. Suppose to the contrary that RR is disconnected, and let AA be the vertex set of one connected component. Add an edge ee joining a vertex in AA to a vertex in V(R)∖AV(R)\setminus A, and denote the enlarged graph by R′R'. Since AA is the vertex set of a component of RR, the existing factor LL gives f(A)=2eL(A)f(A)=2e_L(A), which is even. For any ff-factor MM of R′R', the total degree sum over AA satisfies

f(A)=∑v∈Af(v)=2eM(A)+δM(A),f(A)=\sum_{v\in A}f(v)=2e_M(A)+\delta_M(A),

where δM(A)\delta_M(A) is the number of edges in MM crossing the cut between AA and V(R)∖AV(R)\setminus A. Since 2eM(A)2e_M(A) is even, δM(A)\delta_M(A) has the same parity as f(A)f(A). In R′R', the only edge crossing this cut is the newly added edge ee, so δM(A)∈{0,1}\delta_M(A)\in\{0,1\}. Thus ee cannot be contained in any ff-factor of R′R'. It follows that the set of ff-factors of R′R' is identical to that of RR, so R′R' still has a unique ff-factor. However, ∣E(R′)∣=∣E(R)∣+1>∣E(R)∣|E(R')|=|E(R)|+1>|E(R)|, contradicting the assumption that RR is ff-extremal. Hence the claim holds. □

If RR has no bridge, then it is 2-edge-connected, and by Theorem 2.1, there exists a vertex vv with dR(v)=f(v)>0d_R(v)=f(v)>0, contradicting our assumption. So we assume that RR has a bridge. Let acac be a bridge of RR, and let A,CA,C be the vertex sets of the components of R−{ac}R-\{ac\}, with a∈Aa\in A and c∈Cc\in C. Let ε=1ac∈E(L)\varepsilon=1_{ac\in E(L)}, fA(v)=dL[A](v)f_A(v)=d_{L[A]}(v) for v∈Av\in A, and fC(v)=dL[C](v)f_C(v)=d_{L[C]}(v) for v∈Cv\in C. Note that fA(a)=f(a)−εf_A(a)=f(a)-\varepsilon and fC(c)=f(c)−εf_C(c)=f(c)-\varepsilon, while fA(v)=f(v)f_A(v)=f(v) for all v∈A∖{a}v\in A\setminus\{a\} and fC(v)=f(v)f_C(v)=f(v) for all v∈C∖{c}v\in C\setminus\{c\}.

For any ff-factor MM of RR, by the same parity argument as before, we have

f(A)=2eM(A)+1ac∈E(M).(1)f(A)=2e_M(A)+1_{ac\in E(M)}. \tag*{(1)}

Since the left-hand side is fixed, 1ac∈E(M)1_{ac\in E(M)} is uniquely determined by parity. It therefore equals ε\varepsilon, the value taken by the unique factor LL. In other words, every ff-factor of RR contains the bridge acac if and only if LL does, which establishes a bijection between the ff-factors of RR and pairs consisting of an fAf_A-factor of R[A]R[A] and an fCf_C-factor of R[C]R[C], combined with the fixed status of acac. Since RR has a unique ff-factor, both R[A]R[A] and R[C]R[C] have unique factors for their respective degree functions, namely L[A]L[A] and L[C]L[C]. Moreover, both induced subgraphs are extremal. Indeed, if either side could be replaced by a larger graph with a unique factor for the same degree function, then acac would still be the only edge between AA and CC. Its membership in an ff-factor would still be fixed by the parity identity (1). The same correspondence would therefore yield a larger graph on V(R)V(R) with a unique ff-factor, contradicting the extremality of RR.

We now consider two cases based on whether the bridge belongs to the unique factor.

Case 1: ac∉E(L)ac\notin E(L).

Since ε=0\varepsilon=0, we have fA(a)=f(a)>0f_A(a)=f(a)>0, so fA(v)>0f_A(v)>0 for all v∈Av\in A. By the induction hypothesis, the fAf_A-extremal graph R[A]R[A] contains at least one tight vertex.

By repeatedly applying Lemma 2.3(ii), we may delete tight vertices one by one from R[A]R[A], while preserving the extremal property for the residual degree function. At each stage at which all residual prescribed degrees are positive, the induction hypothesis supplies a tight vertex, since the residual graph has smaller order than RR. We stop as soon as a free vertex appears. Such a vertex must appear before all vertices are deleted: every residual graph has its residual factor, and a factor on a single vertex has degree zero. Therefore, after deleting some sequence of tight vertices s1,s2,…,sjs_1,s_2,\ldots,s_j, we obtain a residual graph containing a free vertex xx.

We now construct a new graph R∗R^* from RR by removing the bridge acac, and adding all edges between xx and vertices in CC. We claim that R∗R^* still has a unique ff-factor. Since ac∉E(L)ac\notin E(L), the only removed edge lies outside LL, so LL remains an ff-factor of R∗R^*. Since x∉{s1,…,sj}x\notin\{s_1,\ldots,s_j\}, no added edge is incident to any sis_i. Moreover, after removing acac and the preceding vertices s1,…,si−1s_1,\ldots,s_{i-1}, the edges incident to sis_i are exactly those at the corresponding stage of the deletion process in R[A]R[A]. The vertex sis_i is therefore tight in R∗R^*, so all its incident edges are forced into any ff-factor. After deleting s1s_1, the same holds for s2s_2, and so on, up to sjs_j. After removing all these tight vertices, the residual prescribed degree of xx is 00, so none of the new edges incident to xx can be contained in any factor. The residual factor on A∖{s1,…,sj}A\setminus\{s_1,\ldots,s_j\} is unique by the repeated applications of Lemma 2.3(ii), and the factor on CC is unique because R[C]R[C] has a unique fCf_C-factor. Hence the ff-factor of R∗R^* is unique.

We now count edges. Note that we removed one edge (namely acac) and added ∣C∣|C| edges. So we have

∣E(R∗)∣=∣E(R)∣−1+∣C∣=∣E(R)∣+(∣C∣−1).|E(R^*)|=|E(R)|-1+|C|=|E(R)|+(|C|-1).

Since ac∉E(L)ac \notin E(L), the graph L[C]L[C] is an f∣Cf|_C-factor of R[C]R[C]. As f(v)>0f(v) > 0 for every v∈Cv \in C, it follows that ∣C∣≥2|C| \ge2. Thus ∣E(R∗)∣>∣E(R)∣|E(R^*)| > |E(R)|. This contradicts the extremality of RR.

Case 2: ac∈E(L)ac \in E(L).

We first assert that f(a)=1f(a) = 1 and f(c)=1f(c) = 1. Suppose for contradiction that f(a)>1f(a) > 1. Then fA(a)=f(a)−1≥1f_A(a) = f(a) - 1 \ge1, so fA(v)>0f_A(v) > 0 for all v∈Av \in A. By induction, R[A]R[A] contains an fAf_A-tight vertex vv. If v≠av \ne a, then dR(v)=dR[A](v)=fA(v)=f(v)d_R(v) = d_{R[A]}(v) = f_A(v) = f(v), which implies that vv is tight in RR, contradicting our assumption. If v=av = a, then dR[A](a)=fA(a)=f(a)−1d_{R[A]}(a) = f_A(a) = f(a) - 1. Consequently,

dR(a)=dR[A](a)+1=fA(a)+1=f(a),d_R(a) = d_{R[A]}(a) + 1 = f_A(a) + 1 = f(a),

which implies that aa is tight in RR, again a contradiction. Hence f(a)=1f(a) = 1, and by symmetry f(c)=1f(c) = 1.

With f(a)=f(c)=1f(a) = f(c) = 1 and ε=1\varepsilon= 1, we have fA(a)=0f_A(a) = 0 and fC(c)=0f_C(c) = 0, which means that aa and cc are two free vertices in R[A]R[A] and R[C]R[C], respectively. By Lemma 2.3(i), free vertices in extremal graphs are universal. Therefore, aa and cc are adjacent to every vertex in A0=A∖{a}A_0 = A \setminus\{a\} and C0=C∖{c}C_0 = C \setminus\{c\}, respectively.

Notice that A0A_0 and C0C_0 are both nonempty. Indeed, if A0=∅A_0 = \varnothing, then aa has only the bridge acac as its incident edge, which implies that dR(a)=1=f(a)d_R(a) = 1 = f(a). Thus aa is a tight vertex, which contradicts our assumption. The same holds for C0C_0.

We now construct a new graph R∗R^* as follows: (i) retain all edges of R[A0]R[A_0] and R[C0]R[C_0], and retain the bridge acac; (ii) join aa to all vertices in A0∪C0A_0 \cup C_0 (retaining the original edges from {a}\{a\} to A0A_0, and adding edges from aa to every vertex in C0C_0); (iii) remove all edges between {c}\{c\} and C0C_0, so that cc is adjacent only to aa; and (iv) choose arbitrary vertices x∈A0x \in A_0 and y∈C0y \in C_0, and add the edge xyxy.

We first verify the edge count. In the original graph RR, there are ∣C0∣|C_0| edges between {c}\{c\} and C0C_0. In R∗R^*, we remove these ∣C0∣|C_0| edges, add ∣C0∣|C_0| edges from {a}\{a\} to C0C_0, and add the edge xyxy. All other edges are unchanged. Since acac was the only edge between AA and CC, the added edges were not contained in RR. Thus, we have

∣E(R∗)∣=∣E(R)∣−∣C0∣+∣C0∣+1=∣E(R)∣+1,|E(R^*)| = |E(R)| - |C_0| + |C_0| + 1 = |E(R)| + 1,

which means that R∗R^* has strictly more edges than RR.

Since ac∈E(L)ac \in E(L) and f(c)=1f(c) = 1, none of the removed edges between {c}\{c\} and C0C_0 belongs to LL. Thus LL remains an ff-factor of R∗R^*. To contradict the extremality of RR, it remains to show that R∗R^* has a unique ff-factor. Since dR∗(c)=1d_{R^*}(c) = 1 and f(c)=1f(c) = 1, the edge acac must be included in every ff-factor. Since f(a)=1f(a) = 1, including acac gives aa its prescribed degree. Thus no other edge incident to aa can belong to any ff-factor. After excluding all other edges incident to aa, the only edge still available to a factor across the cut between A0A_0 and V(R∗)∖A0V(R^*) \setminus A_0 is xyxy. The sum of the prescribed degrees on A0A_0 is f(A0)=2eL(A0)f(A_0) = 2e_L(A_0), which is even. Any factor must use an even number of edges across this cut, so the single edge xyxy cannot be contained in the factor. Consequently, apart from acac, every edge of an ff-factor belongs to R[A0]R[A_0] or R[C0]R[C_0]. By Lemma 2.3(i) applied to the free vertices aa and cc of R[A]R[A] and R[C]R[C], respectively, each of these graphs has a unique factor for the restriction of ff. Together with the forced edge acac, these two factors determine the unique ff-factor of R∗R^*, contradicting the extremality of RR.

The proof of Theorem 2.4 is complete.

If a vertex of prescribed degree zero is present, then use Lemma 2.3(i); otherwise use Theorem 2.4 and Lemma 2.3(ii). Repeating this process until the vertex set is exhausted, we obtain the following corollary.

Its vertices admit an ordering v1,…,v∣V(R)∣v_1,\ldots,v_{|V(R)|} such that, with Ri=R[{vi,…,v∣V(R)∣}]R_i=R[\{v_i,\ldots,v_{|V(R)|}\}], Li=L[{vi,…,v∣V(R)∣}]L_i=L[\{v_i,\ldots,v_{|V(R)|}\}], and fi(v)=dLi(v)f_i(v)=d_{L_i}(v), each RiR_i is fif_i-extremal, and viv_i is either free and universal in RiR_i, or tight in RiR_i.

Proof of Theorem 1.2

We first prove an inequality for a bipartite graph whose vertices in one partite set are ordered.

Lemma 3.1. Let Γ\Gamma be a bipartite graph with partite sets UU and Q={1,…,z}Q=\{1,\ldots,z\} such that dΓ(v)=k≥1d_\Gamma(v)=k\ge1 for each v∈Qv\in Q. If ∣U∣=t|U|=t and d1≤⋯≤dtd_1\le\cdots\le d_t is the nondecreasing degree sequence on UU, then

∑u∈Uc(u)≥∑i=1tdi+∑i=1t⌊t−ik⌋di\sum_{u\in U}c(u)\ge\sum_{i=1}^{t}d_i+\sum_{i=1}^{t}\left\lfloor\frac{t-i}{k}\right\rfloor d_i

where c(u)=max⁡(NΓ(u)∪{0})c(u)=\max\left(N_\Gamma(u)\cup\{0\}\right) for u∈Uu\in U.

Proof. If z=0z=0, then both sides are zero. So we may assume that z≥1z\ge1. We form the bipartite graph HH with two partite sets UU and QQ, and with uv∈E(H)uv\in E(H) if and only if 1≤v≤c(u)1\le v\le c(u). Note that Γ⊆H\Gamma\subseteq H.

Claim 2. For every X⊆UX\subseteq U, ∑u∈XdΓ(u)≤∑v=1zmin⁡{k,∣NH(v)∩X∣}\sum_{u\in X}d_\Gamma(u)\le\sum_{v=1}^{z}\min\{k,|N_H(v)\cap X|\}.

Proof of Claim 2. For every v∈Qv\in Q, the inclusion Γ⊆H\Gamma\subseteq H and the equality dΓ(v)=kd_\Gamma(v)=k show that

∣NΓ(v)∩X∣≤min⁡{k,∣NH(v)∩X∣}.|N_\Gamma(v)\cap X|\le\min\{k,|N_H(v)\cap X|\}.

Counting the edges of Γ\Gamma between XX and QQ from each partite set, we obtain that

∑u∈XdΓ(u)=∑v=1z∣NΓ(v)∩X∣≤∑v=1zmin⁡{k,∣NH(v)∩X∣}.\sum_{u\in X}d_\Gamma(u)=\sum_{v=1}^{z}|N_\Gamma(v)\cap X|\le\sum_{v=1}^{z}\min\{k,|N_H(v)\cap X|\}.

This proves the claim.

Let u1,…,utu_1,\ldots,u_t be an ordering of UU so that c(u1)≥⋯≥c(ut)c(u_1)\ge\cdots\ge c(u_t). For v∈Qv\in Q, let Nv=∣NH(v)∣=∣{u∈U:c(u)≥v}∣N_v=|N_H(v)|=|\{u\in U:c(u)\ge v\}|. Then k≤Nv≤tk\le N_v\le t. Indeed, since dΓ(v)=kd_\Gamma(v)=k, the vertex vv has kk neighbors uu in Γ\Gamma, and each such neighbor satisfies c(u)≥vc(u)\ge v. Moreover, we have NH(v)={u1,…,uNv}N_H(v)=\{u_1,\ldots,u_{N_v}\}, and

∑u∈Uc(u)=∑u∈U∑v=1c(u)1=∑v=1z∑u:c(u)≥v1=∑v=1zNv.(2)\sum_{u\in U}c(u)=\sum_{u\in U}\sum_{v=1}^{c(u)}1=\sum_{v=1}^{z}\sum_{u:c(u)\ge v}1=\sum_{v=1}^{z}N_v. \tag*{(2)}

Write r+=max⁡{r,0}r_+=\max\{r,0\}. For every integer h≥1h\ge1, define Xh={ui:hk<i≤t}X_h=\{u_i:hk<i\le t\}. Thus ∣Xh∣=(t−hk)+|X_h|=(t-hk)_+. When hk<thk<t, this is a set of t−hkt-hk vertices with the smallest values of c(u)c(u); when hk≥thk\ge t, it is empty.

We now apply the inequality in Claim 2 to a family of subsets XhX_h of UU. Since NH(v)={u1,…,uNv}N_H(v)=\{u_1,\ldots,u_{N_v}\}, its intersection with XhX_h consists of those uiu_i with hk<i≤Nvhk<i\le N_v. Therefore ∣NH(v)∩Xh∣=(Nv−hk)+|N_H(v)\cap X_h|=(N_v-hk)_+. Note that every subset of UU of size (t−hk)+(t-hk)_+ has degree sum at least the sum of the (t−hk)+(t-hk)_+ smallest degrees. Hence

∑u∈XhdΓ(u)≥∑i=1(t−hk)+di.(3)\sum_{u\in X_h}d_\Gamma(u)\ge\sum_{i=1}^{(t-hk)_+}d_i. \tag*{(3)}

Substituting X=XhX=X_h into the inequality in Claim 2 and combining with the above identities, we obtain that

∑i=1(t−hk)+di≤∑v=1zmin⁡{k,(Nv−hk)+}.(4)\sum_{i=1}^{(t-hk)_{+}} d_i \le\sum_{v=1}^{z} \min\{k,(N_v-hk)_{+}\}. \tag*{(4)}

For every integer N≥kN\ge k, we have

∑h≥1min⁡{k,(N−hk)+}=N−k.\sum_{h\ge1}\min\{k,(N-hk)_{+}\}=N-k.

Indeed, write N=ak+bN=ak+b with integers a≥1a\ge1 and 0≤b<k0\le b<k. If 1≤h≤a−11\le h\le a-1, then N−hk≥kN-hk\ge k, so min⁡{k,N−hk}=k\min\{k,N-hk\}=k; this contributes a−1a-1 terms equal to kk. If h=ah=a, then N−ak=bN-ak=b, which implies that min⁡{k,b}=b\min\{k,b\}=b. If h>ah>a, then N−hk<0N-hk<0, so (N−hk)+=0(N-hk)_{+}=0 and the summand vanishes. Summing these contributions, we obtain

(a−1)k+b=ak+b−k=N−k.(a-1)k+b=ak+b-k=N-k.

For hk≥thk\ge t, both sides of (3.2) are zero. Thus we may sum (3.2) over all h≥1h\ge1; all sums involved have only finitely many nonzero terms. On the right-hand side we interchange the order of summation and apply the identity for each vv,

∑h≥1∑v=1zmin⁡{k,(Nv−hk)+}=∑v=1z∑h≥1min⁡{k,(Nv−hk)+}=∑v=1z(Nv−k).\sum_{h\ge1}\sum_{v=1}^{z}\min\{k,(N_v-hk)_{+}\}=\sum_{v=1}^{z}\sum_{h\ge1}\min\{k,(N_v-hk)_{+}\}=\sum_{v=1}^{z}(N_v-k).

Using (2), this simplifies to

∑v=1zNv−kz=∑u∈Uc(u)−kz.(5)\sum_{v=1}^{z}N_v-kz=\sum_{u\in U}c(u)-kz. \tag*{(5)}

The sum of the left-hand side of (3.2) over h≥1h\ge1 is ∑h≥1∑i=1(t−hk)+di\sum_{h\ge1}\sum_{i=1}^{(t-hk)_{+}}d_i. For a fixed index ii, the term did_i appears in the inner sum if and only if i≤t−hki\le t-hk, or equivalently h≤(t−i)/kh\le(t-i)/k. Since hh runs over positive integers, the number of such indices hh is exactly ⌊(t−i)/k⌋\left\lfloor(t-i)/k\right\rfloor. Interchanging the order of summation, we have

∑h≥1∑i=1(t−hk)+di=∑i=1t⌊t−ik⌋di.(6)\sum_{h\ge1}\sum_{i=1}^{(t-hk)_{+}}d_i=\sum_{i=1}^{t}\left\lfloor\frac{t-i}{k}\right\rfloor d_i. \tag*{(6)}

Combining (3.2), (5), and (6), we have

∑i=1t⌊t−ik⌋di=∑h≥1∑i=1(t−hk)+di≤∑h≥1∑v=1zmin⁡{k,(Nv−hk)+}=∑v=1zNv−kz=∑u∈Uc(u)−kz.(7)\begin{aligned} \sum_{i=1}^{t}\left\lfloor\frac{t-i}{k}\right\rfloor d_i &=\sum_{h\ge1}\sum_{i=1}^{(t-hk)_{+}}d_i\\ &\le\sum_{h\ge1}\sum_{v=1}^{z}\min\{k,(N_v-hk)_{+}\}\\ &=\sum_{v=1}^{z}N_v-kz=\sum_{u\in U}c(u)-kz. \tag*{(7)} \end{aligned}

By the handshaking lemma for bipartite graphs, the total degree sum over QQ equals the total degree sum over UU, i.e.,

kz=∑v∈QdΓ(v)=∑u∈UdΓ(u)=∑i=1tdi.kz=\sum_{v\in Q}d_{\Gamma}(v)=\sum_{u\in U}d_{\Gamma}(u)=\sum_{i=1}^{t}d_i.

Substituting the above equality into (7), we have

∑u∈Uc(u)≥∑i=1tdi+∑i=1t⌊t−ik⌋di\sum_{u\in U} c(u) \ge\sum_{i=1}^{t} d_i+\sum_{i=1}^{t}\left\lfloor\frac{t-i}{k}\right\rfloor d_i

This completes the proof of Lemma 3.1.

Let kk and nn be two positive integers such that knkn is even and 2k+1≤n≤3k2k+1\le n\le3k. To establish a lower bound for m(n,k)m(n,k), we introduce some families of graphs of order nn with a unique kk-factor.

Example 3.2 (see Example 3.1 in [10]). Let kk and rr be positive integers. We construct the graph Q(n,k)Q(n,k) that is of size k2+(n−k2)k^2+\binom{n-k}{2} and has a unique kk-factor by considering two cases. In both cases, the prescribed degrees on BB lie between 00 and kk and sum to k2k^2. To realize them, list the kk vertices of AA cyclically kk times, partition the list into consecutive segments of the prescribed lengths, and join each vertex of BB to its segment. Each segment has distinct entries, and every vertex of AA has degree kk.

Case 1. n=2k+2rn=2k+2r and 2r≤k2r\le k. Let HH be the bipartite graph with the partite sets AA and BB such that ∣A∣=k|A|=k and ∣B∣=k+2r|B|=k+2r with

B={u1,u2,…,u2r−1}∪{v1,v2,…,vk−2r+1}∪{w1,w2,…,wr}∪{y1,y2,…,yr}.B=\{u_1,u_2,\ldots,u_{2r-1}\}\cup\{v_1,v_2,\ldots,v_{k-2r+1}\} \cup\{w_1,w_2,\ldots,w_r\}\cup\{y_1,y_2,\ldots,y_r\}.

Next we connect the vertices of AA and BB by edges such that dH(x)=kd_H(x)=k for all x∈Ax\in A, dH(ui)=kd_H(u_i)=k for 1≤i≤2r−11\le i\le2r-1, dH(vi)=k−rd_H(v_i)=k-r for 1≤i≤k−2r+11\le i\le k-2r+1, dH(wi)=k−2r+1d_H(w_i)=k-2r+1 for 1≤i≤r1\le i\le r, and dH(yi)=0d_H(y_i)=0 for 1≤i≤r1\le i\le r. It is a simple matter to see that one can realize such a bipartite graph and

∑x∈AdH(x)=∑x∈BdH(x)=k2.\sum_{x\in A}d_H(x)=\sum_{x\in B}d_H(x)=k^2.

Now the graph Q(n,k)Q(n,k) of order n=2k+2rn=2k+2r originates from HH by connecting all pairs of vertices in BB by an edge. Every kk-factor contains all edges of HH, since every vertex of AA has degree kk. The vertices uiu_i therefore have degree zero in the remaining factor on BB. Each yiy_i must be adjacent in this factor to all other vertices of B∖{u1,…,u2r−1}B\setminus\{u_1,\ldots,u_{2r-1}\}, which has order k+1k+1. This gives every viv_i its remaining degree rr, and forces the vertices wiw_i to induce KrK_r. Thus the remaining factor, and hence the kk-factor of Q(n,k)Q(n,k), exists and is unique.

Case 2. n=2k+2r−1n=2k+2r-1 with 2r≤k+12r\le k+1 and k=2qk=2q even. Let HH be the bipartite graph with the partite sets AA and BB such that ∣A∣=k|A|=k and ∣B∣=k+2r−1|B|=k+2r-1 with

B={u1,u2,…,uq+r−1}∪{v1,v2,…,vq−r+1}∪{w1,w2,…,w2r−1}.B=\{u_1,u_2,\ldots,u_{q+r-1}\}\cup\{v_1,v_2,\ldots,v_{q-r+1}\}\cup\{w_1,w_2,\ldots,w_{2r-1}\}.

Next we connect the vertices of AA and BB by edges such that dH(x)=kd_H(x)=k for all x∈Ax\in A, dH(ui)=kd_H(u_i)=k for 1≤i≤q+r−11\le i\le q+r-1, dH(vi)=k−2r+1d_H(v_i)=k-2r+1 for 1≤i≤q−r+11\le i\le q-r+1, and dH(wi)=q−r+1d_H(w_i)=q-r+1 for 1≤i≤2r−11\le i\le2r-1. Clearly, one can realize such a bipartite graph and

∑x∈AdH(x)=∑x∈BdH(x)=k2.\sum_{x\in A}d_H(x)=\sum_{x\in B}d_H(x)=k^2.

Now the graph Q(n,k)Q(n,k) of order n=2k+2r−1n=2k+2r-1 originates from HH by connecting all pairs of vertices in BB by an edge. Again, every kk-factor contains all edges of HH, and the vertices

uiu_i have degree zero in the remaining factor on BB. Each wiw_i must be adjacent in this factor to all other vertices of B∖{u1,…,uq+r−1}B \setminus\{u_1,\ldots,u_{q+r-1}\}, which has order q+rq+r. These edges give every viv_i its remaining degree 2r−12r-1. Thus the remaining factor exists and is unique in this case as well.

We next introduce another family of graphs H(n,k)H(n,k).

Example 3.3 (see Example 5.1 in [10]). For k<n≤2kk<n\le2k with nknk even, if PP is a (2k−n)(2k-n)-regular graph of order kk, then the graph R(n,k)=P+K‾n−kR(n,k)=P+\overline{K}_{n-k} is of size nk/2+(n−k2)nk/2+\binom{n-k}{2} and has a unique kk-factor. Such a graph PP exists since 0≤2k−n≤k−10\le2k-n\le k-1 and k(2k−n)=2k2−nkk(2k-n)=2k^2-nk is even. Now let nn, kk, and qq be positive integers such that n>2kn>2k and n=2kq+rn=2kq+r with 0≤r<2k0\le r<2k and nknk even. Construct different families of graphs H(n,k)H(n,k) of order nn as follows: take q−1q-1 disjoint copies of Kk+K‾kK_k+\overline{K}_k labelled H1,H2,…,Hq−1H_1,H_2,\ldots,H_{q-1}.

  • Case 1. For r=0r=0 define Hq=Kk+K‾kH_q=K_k+\overline{K}_k.

  • Case 2. For 1≤r≤k1\le r\le k define Hq=Q(2k+r,k)H_q=Q(2k+r,k) (cf. Example 3.2).

  • Case 3. For k+1≤r<2kk+1\le r<2k define Hq=Kk+K‾kH_q=K_k+\overline{K}_k and Hq+1=R(r,k)H_{q+1}=R(r,k).

For each ii and jj with 1≤i<j≤q1\le i<j\le q in the first two cases and 1≤i<j≤q+11\le i<j\le q+1 in the third case, add the edges connecting all vertices of the KkK_k in HiH_i to all the vertices of HjH_j. It can easily be verified that H(n,k)H(n,k) has a unique kk-factor, and its size is h(n,k)h(n,k).

For n>2kn>2k, the construction uses ordered blocks. A standard block has two sets Ai,BiA_i,B_i of size kk, with AiA_i independent, BiB_i complete, and all edges between them. Its unique kk-factor is Kk,kK_{k,k}. Add all edges from BiB_i to every later block.

When r=0r=0, use qq standard blocks. When 1≤r≤k1\le r\le k, use q−1q-1 standard blocks followed by the graph Q(2k+r,k)Q(2k+r,k). When k+1≤r<2kk+1\le r<2k, use qq standard blocks followed by Hendry’s graph R(r,k)R(r,k). In the range k<n≤2kk<n\le2k, use R(n,k)R(n,k) itself, with R(2k,k)R(2k,k) understood as a standard block.

The degree-kk vertices in the first standard block force its Kk,kK_{k,k} factor, giving every vertex of that block degree kk in the factor. No edge from that block to a later block can be used. Repetition reduces uniqueness to the last block. Counting the edges gives h(n,k)h(n,k), as in Example 3.3. Indeed, prepending a standard block to a graph of order N−2kN-2k adds

k2+(k2)+k(N−2k)=kN−k(k+1)2=h(N,k)−h(N−2k,k)k^2+\binom{k}{2}+k(N-2k)=kN-\frac{k(k+1)}{2}=h(N,k)-h(N-2k,k)

edges; the final blocks have the stated sizes. In particular,

m(n,k)≥h(n,k).(8)m(n,k)\ge h(n,k). \tag*{(8)}

Proof of Theorem 1.2. Let GG be a graph of order nn and size m(n,k)m(n,k) with unique kk-factor FF. Color the edges of FF red and all other edges of GG blue. Write n=2kq+rn=2kq+r, where q≥0q\ge0 and 0≤r<2k0\le r<2k. Use the ordering v1,…,vnv_1,\ldots,v_n from Corollary 2.5. Let ai=dF[{vi,…,vn}](vi)a_i=d_{F[\{v_i,\ldots,v_n\}]}(v_i). Call the deletion of viv_i free when ai=0a_i=0 and tight otherwise. At each step, a free vertex is universal in the remaining graph, while a tight vertex has remaining degree aia_i. Let s1,…,szs_1,\ldots,s_z be the free vertices in deletion order, with positions p1<⋯<pzp_1<\cdots<p_z, and let TT be the set of the other t=n−zt=n-z vertices.

If i<ji<j and viv_i is free, then vivjv_iv_j is blue; and if viv_i is tight, every remaining edge incident to viv_i is red. Consequently, with B=∣Eb∣B=|E_b|, we have

B=∑i:ai=0(n−i)=∑j=1z(n−pj).(9)B=\sum_{i:a_i=0}(n-i)=\sum_{j=1}^{z}(n-p_j). \tag*{(9)}

Note that the free vertices are independent in FF. Indeed, the earlier endpoint of a red edge between two free vertices would have positive residual factor degree when deleted, contradicting the definition of a free deletion.

Let Xj=Nr({s1,…,sj})⊆TX_j=N_{\mathrm{r}}(\{s_1,\ldots,s_j\})\subseteq T, xj=∣Xj∣x_j=|X_j|, and C=∑j=1zxjC=\sum_{j=1}^{z}x_j. Note that pj≥j+xjp_j\ge j+x_j, since every red neighbor of shs_h precedes shs_h, and hence every vertex of XjX_j precedes sjs_j. So by (9), we have

B=∑j=1z(n−pj)≤∑j=1z(n−j−xj)=zn−(z+12)−C.(10)B=\sum_{j=1}^{z}(n-p_j)\le\sum_{j=1}^{z}(n-j-x_j)=zn-\binom{z+1}{2}-C. \tag*{(10)}

We now construct an auxiliary bipartite graph to apply Lemma 3.1. For u∈Tu\in T, let d(u)d(u) be the number of red neighbors among the free vertices. Since each free vertex has kk red neighbors, we have ∑u∈Td(u)=kz\sum_{u\in T}d(u)=kz. Define a bipartite graph Γ\Gamma with partite sets TT and {1,…,z}\{1,\ldots,z\} by joining u∈Tu\in T to v∈{1,…,z}v\in\{1,\ldots,z\} when uu is a red neighbor of sz−v+1s_{z-v+1}. Every vertex in the second partite set has degree kk. As in Lemma 3.1, set c(u)=max⁡(NΓ(u)∪{0})c(u)=\max(N_{\Gamma}(u)\cup\{0\}). Double-counting the pairs (u,j)(u,j) with u∈Xju\in X_j shows C=∑u∈Tc(u)C=\sum_{u\in T}c(u), since, if sjs_j is the first free red neighbor of uu, then uu belongs to exactly Xj,…,XzX_j,\ldots,X_z and c(u)=z−j+1c(u)=z-j+1; if uu has no free red neighbor, both contributions are zero.

Let d1≤⋯≤dtd_1\le\cdots\le d_t be the degree sequence of Γ\Gamma on TT, and let ρi=k−di\rho_i=k-d_i, wi=⌊(t−i)/k⌋w_i=\lfloor(t-i)/k\rfloor, ℓ=t−z=n−2z\ell=t-z=n-2z, and Φ=∑i=1twiρi\Phi=\sum_{i=1}^{t}w_i\rho_i. Then ρ1≥⋯≥ρt\rho_1\ge\cdots\ge\rho_t is the non-increasing degree sequence of F[T]F[T],

∑i=1tρi=kt−kz=k(n−2z)=kℓ,\sum_{i=1}^{t}\rho_i=kt-kz=k(n-2z)=k\ell,

and 0≤ℓ≤t0\le\ell\le t (since combining d(u)≤kd(u)\le k and ∑u∈Td(u)=kz\sum_{u\in T}d(u)=kz gives z≤tz\le t). By Lemma 3.1, we have

C≥kz+k∑i=1twi−Φ.(11)C\ge kz+k\sum_{i=1}^{t}w_i-\Phi. \tag*{(11)}

For 1≤j≤t1\le j\le t, write Dj=∑i=1jρiD_j=\sum_{i=1}^{j}\rho_i. Then by the same counting argument as in Lemma 3.1, we have

Φ=∑h=1⌊(t−1)/k⌋Dt−hk.(12)\Phi=\sum_{h=1}^{\lfloor(t-1)/k\rfloor}D_{t-hk}. \tag*{(12)}

Let YY be a set of jj vertices of largest degree in F[T]F[T]. Write Dj=∑u∈YdF[T](u)D_j=\sum_{u\in Y}d_{F[T]}(u). We decompose the degree sum over YY as

Dj=2eF[T](Y)+eF[T](Y,T∖Y).D_j=2e_{F[T]}(Y)+e_{F[T]}(Y,T\setminus Y).

The degree sum over the complement is

kℓ−Dj=2eF[T](T∖Y)+eF[T](Y,T∖Y),k\ell-D_j=2e_{F[T]}(T\setminus Y)+e_{F[T]}(Y,T\setminus Y),

which implies that kℓ−Dj≥eF[T](Y,T∖Y)k\ell-D_j\ge e_{F[T]}(Y,T\setminus Y). Since F[T]F[T] is simple, 2eF[T](Y)≤j(j−1)2e_{F[T]}(Y)\le j(j-1). Therefore

Dj≤j(j−1)+eF[T](Y,T∖Y)≤j(j−1)+(kℓ−Dj),D_j\le j(j-1)+e_{F[T]}(Y,T\setminus Y)\le j(j-1)+(k\ell-D_j),

i.e., 2Dj≤kℓ+j(j−1)2D_j\le k\ell+j(j-1). Moreover, each vertex in F[T]F[T] has degree at most kk, so Dj≤kjD_j\le kj, and the total degree sum of F[T]F[T] is kℓk\ell, so Dj≤kℓD_j\le k\ell. Thus

Dj≤min⁡{kj,kℓ,kℓ+j(j−1)2}.(13)D_j\le\min\left\{kj,k\ell,\frac{k\ell+j(j-1)}{2}\right\}. \tag*{(13)}

To bound Φ\Phi, we first use only the numerical constraints 0≤ρi≤k0 \le\rho_i \le k and ∑iρi=kℓ\sum_i \rho_i = k\ell, together with the fact that the weights wiw_i are non-increasing. Under these numerical constraints, if i<ji<j, ρi<k\rho_i<k, and ρj>0\rho_j>0, replace ρi\rho_i and ρj\rho_j by ρi+δ\rho_i+\delta and ρj−δ\rho_j-\delta, respectively, where δ=min⁡{k−ρi,ρj}\delta=\min\{k-\rho_i,\rho_j\}. This preserves the constraints and does not decrease the weighted sum. Repeating these exchanges, we obtain kk in each of the first ℓ\ell positions and 00 in all remaining positions. Hence Φ≤k∑i=1ℓwi\Phi\le k\sum_{i=1}^{\ell}w_i. By (11), we have

C≥kz+k∑i=ℓ+1twi=k∑j=1z⌈jk⌉=:C0(z,k).(14)C \ge kz+k\sum_{i=\ell+1}^{t}w_i=k\sum_{j=1}^{z}\left\lceil\frac{j}{k}\right\rceil=:C_0(z,k). \tag*{(14)}

Here the equality uses t−ℓ=zt-\ell=z and 1+⌊(j−1)/k⌋=⌈j/k⌉1+\lfloor(j-1)/k\rfloor=\lceil j/k\rceil. Combining (10) and (14), we have

B≤Un,k(z):=zn−(z+12)−C0(z,k).(15)B\le U_{n,k}(z):=zn-\binom{z+1}{2}-C_0(z,k). \tag*{(15)}

Then the first difference is

Un,k(z+1)−Un,k(z)=n−z−1−k⌈z+1k⌉,(16)U_{n,k}(z+1)-U_{n,k}(z)=n-z-1-k\left\lceil\frac{z+1}{k}\right\rceil, \tag*{(16)}

which is strictly decreasing in zz.

Let J=n(n−k−1)/4J=n(n-k-1)/4, and let β=h(n,k)−nk/2=J−ϑk(r)/4\beta=h(n,k)-nk/2=J-\vartheta_k(r)/4. If z=ak+bz=ak+b, with 0≤b<k0\le b<k, then

C0(z,k)=k2a(a+1)2+kb(a+1).C_0(z,k)=\frac{k^2a(a+1)}{2}+kb(a+1).

Using n=2z+ℓn=2z+\ell and the expansion of (15), we obtain that

J−Un,k(z)=ℓ(ℓ−k−1)+2b(k−b)4.(17)J-U_{n,k}(z)=\frac{\ell(\ell-k-1)+2b(k-b)}{4}. \tag*{(17)}

Suppose first that k<n≤2kk<n\le2k, and let h0=n−kh_0=n-k. If z=0z=0, then B=0B=0; and if z≥1z\ge1, then the kk red neighbors of each free vertex belong to TT, giving z≤n−k=h0≤kz\le n-k=h_0\le k. In this range ⌈j/k⌉=1\lceil j/k\rceil=1 (1≤j≤z1\le j\le z), and hence C0(z,k)=kzC_0(z,k)=kz. So

B≤zn−(z+12)−kz=zh0−(z+12)=(h02)−(h0−z2)≤(n−k2).B\le zn-\binom{z+1}{2}-kz=zh_0-\binom{z+1}{2}=\binom{h_0}{2}-\binom{h_0-z}{2}\le\binom{n-k}{2}.

It follows that ∣E(G)∣≤nk/2+(n−k2)=h(n,k)|E(G)|\le nk/2+\binom{n-k}{2}=h(n,k), including n=2kn=2k.

Now assume that n>2kn>2k. If r=0r=0, then we let z0=kqz_0=kq. By (16),

Un,k(z0)−Un,k(z0−1)=n−z0−k⌈z0k⌉=2kq−kq−kq=0,U_{n,k}(z_0)-U_{n,k}(z_0-1)=n-z_0-k\left\lceil\frac{z_0}{k}\right\rceil=2kq-kq-kq=0,

which, since the first differences are strictly decreasing, shows that z0−1z_0-1 and z0z_0 maximize Un,kU_{n,k}. At z0z_0, we have ℓ=b=0\ell=b=0. So by (17), we obtain that B≤Un,k(z0)=J=βB\le U_{n,k}(z_0)=J=\beta.

If k<r<2kk<r<2k, then we let z0=kq+r−kz_0=kq+r-k. Since ⌈z0/k⌉=q+1\lceil z_0/k\rceil=q+1, by (16), we have

Un,k(z0)−Un,k(z0−1)=n−z0−k(q+1)=0.U_{n,k}(z_0)-U_{n,k}(z_0-1)=n-z_0-k(q+1)=0.

Thus z0−1z_0-1 and z0z_0 again maximize Un,kU_{n,k}. At z0z_0, we have ℓ=2k−r\ell=2k-r and b=r−kb=r-k, whence, by (17),

J−Un,k(z0)=(r−k−1)(2k−r)4.J-U_{n,k}(z_0)=\frac{(r-k-1)(2k-r)}{4}.

Therefore B≤βB \le\beta also holds.

It remains to consider 1≤r≤k1 \le r \le k. We discuss two cases according to ℓ\ell.

Case 1: ℓ≥k+1\ell\ge k+1.

Since k⌈(z+1)/k⌉≤z+kk\lceil(z+1)/k\rceil\le z+k, by (16), we have Un,k(z+1)−Un,k(z)≥ℓ−k−1U_{n,k}(z+1)-U_{n,k}(z) \ge\ell-k-1. Thus Un,k(z)U_{n,k}(z) is nondecreasing on the integer range n−2z≥k+1n-2z \ge k+1. Let ℓ0\ell_0 be the least integer at least k+1k+1 of the same parity as nn. Let ℓ0=k+ε\ell_0=k+\varepsilon, where

ε={1,if r≠k(mod2),2,if r≡k(mod2).\varepsilon= \begin{cases} 1, & \text{if } r \ne k \pmod{2},\\ 2, & \text{if } r \equiv k \pmod{2}. \end{cases}

The largest zz in this range is z0=(n−ℓ0)/2=k(q−1)+bz_0=(n-\ell_0)/2=k(q-1)+b, and b=(r+k−ε)/2b=(r+k-\varepsilon)/2, where 0≤b<k0 \le b<k. Subtracting ϑk(r)/4=r(k+1−r)/4\vartheta_k(r)/4=r(k+1-r)/4 from (17), we have

β−Un,k(z0)={(k−r)2−18,if ε=1,(k−r)2+2(k+r)8,if ε=2.\beta-U_{n,k}(z_0)= \begin{cases} \dfrac{(k-r)^2-1}{8}, & \text{if } \varepsilon=1,\\[6pt] \dfrac{(k-r)^2+2(k+r)}{8}, & \text{if } \varepsilon=2. \end{cases}

When ε=1\varepsilon=1, k−rk-r is a positive odd integer, so the first expression is nonnegative. When ε=2\varepsilon=2, the second expression is positive. Hence B≤Un,k(z)≤Un,k(z0)≤βB \le U_{n,k}(z) \le U_{n,k}(z_0) \le\beta.

Case 2: 0≤ℓ≤k0 \le\ell\le k.

Write t=ak+st=ak+s, where a≥1a\ge1 and 1≤s≤k1\le s\le k; if kk divides tt, take s=ks=k. Here a≥1a\ge1 since t=(n+ℓ)/2>kt=(n+\ell)/2>k. In particular, a=⌊(t−1)/k⌋a=\lfloor(t-1)/k\rfloor, and (12) can be rewritten as Φ=∑j=0a−1Djk+s\Phi=\sum_{j=0}^{a-1}D_{jk+s}. In (12), all the partial sums except the last have indices at least k+1k+1, and the last is DsD_s. Apply Dj≤kℓD_j\le k\ell to the first a−1a-1 partial sums, and apply (13) to DsD_s, to obtain that

Φ≤(a−1)kℓ+kℓ+s(s−1)2.(18)\Phi\le(a-1)k\ell+\frac{k\ell+s(s-1)}{2}. \tag*{(18)}

Also,

∑i=1twi=∑m=0ak+s−1⌊mk⌋=k(0+1+⋯+(a−1))+as=as+ka(a−1)2.(19)\sum_{i=1}^{t}w_i=\sum_{m=0}^{ak+s-1}\left\lfloor\frac{m}{k}\right\rfloor =k(0+1+\cdots+(a-1))+as =as+\frac{ka(a-1)}{2}. \tag*{(19)}

Substituting (18) and (19) into (11) and then (10), and using z=ak+s−ℓz=ak+s-\ell, we obtain that

4(J−B)≥ℓ(ℓ−k−1)−2z(z+k)+4C≥ℓ(ℓ−k−1)−2z(z+k)+4kz+4k(as+ka(a−1)2)−4(a−1)kℓ−2kℓ−2s(s−1)=(2s−ℓ)(k+1−2s+ℓ).\begin{aligned} 4(J-B)&\ge\ell(\ell-k-1)-2z(z+k)+4C\\ &\ge\ell(\ell-k-1)-2z(z+k)+4kz+4k\left(as+\frac{ka(a-1)}{2}\right)\\ &\qquad-4(a-1)k\ell-2k\ell-2s(s-1)\\ &=(2s-\ell)(k+1-2s+\ell). \end{aligned}

Since n=2z+ℓ=2ak+2s−ℓn=2z+\ell=2ak+2s-\ell and n=2kq+rn=2kq+r, we have 2s−ℓ≡r(mod2k)2s-\ell\equiv r\pmod{2k}. On the other hand, since 1≤s≤k1\le s\le k and 0≤ℓ≤k0\le\ell\le k, 2−k≤2s−ℓ≤2k2-k\le2s-\ell\le2k. For 1≤r≤k1\le r\le k, we have r−2k≤−k<2−kr-2k\le-k<2-k and r+2k>2kr+2k>2k. Thus the only integer in this interval congruent to rr modulo 2k2k is rr itself, so 2s−ℓ=r2s-\ell=r. Therefore J−B≥r(k+1−r)/4J-B\ge r(k+1-r)/4, which is exactly B≤βB\le\beta.

Since the unique factor has nk/2nk/2 edges,

m(n,k)=∣E(G)∣=nk2+B≤h(n,k).m(n,k)=|E(G)|=\frac{nk}{2}+B\le h(n,k).

The examples in this section give m(n,k)≥h(n,k)m(n,k)\ge h(n,k). Hence m(n,k)=h(n,k)m(n,k)=h(n,k). The proof of Theorem 1.2 is complete.

Proof of Theorem 1.4

The proof of Theorem 1.4 relies on the deletion ordering from Corollary 2.5 and the extremal deletion properties from Lemma 2.3.

Proof of Theorem 1.4. Starting from GG with the unique kk-factor FF, we repeatedly delete tight vertices following the deletion ordering from Corollary 2.5, stopping at the first free deletion. Such a step must occur, since the residual factor on the last remaining vertex has degree zero. Let t1,…,tht_1,\ldots,t_h be the vertices deleted before this step, listed in deletion order, and let T0={t1,…,th}T_0 = \{t_1,\ldots,t_h\}. Let xx be the vertex deleted at this first free step.

By Lemma 2.3(ii), every edge incident to a tight vertex in the corresponding residual graph belongs to the residual factor (i.e., is a red edge). For every edge of GG incident to a vertex of T0T_0, its earlier endpoint in the deletion ordering also belongs to T0T_0. The edge is still present when that endpoint is deleted tightly, so it is red. As a result, every vertex in T0T_0 has degree exactly kk in the original graph GG.

Claim 3. ∣T0∣=k|T_0| = k.

Proof of Claim 3. We first show that ∣T0∣≥k|T_0| \ge k. Note that the initial factor degree of xx is kk, and its residual prescribed degree becomes 00 after deleting the vertex set T0T_0. Thus Nr(x)⊆T0N_r(x) \subseteq T_0, and ∣Nr(x)∣=dF(x)=k|N_r(x)| = d_F(x) = k. Therefore ∣T0∣≥k|T_0| \ge k.

Next we prove that ∣T0∣≤k|T_0| \le k by contradiction. Suppose that ∣T0∣>k|T_0| > k. We construct an enlarged graph G′G' by adding all edges from xx to vertices in T0∖Nr(x)T_0 \setminus N_r(x). These edges are not in GG. Indeed, otherwise, if a vertex u∈T0∖Nr(x)u \in T_0 \setminus N_r(x) were adjacent to xx, then xuxu would be red, contrary to u∉Nr(x)u \notin N_r(x).

We now verify that G′G' has a unique kk-factor. Since no edge is removed, FF remains a kk-factor of G′G'. The kk vertices in Nr(x)⊆T0N_r(x) \subseteq T_0 are unaffected by the newly added edges, so they still have degree kk in G′G'. Consequently, all their incident edges must be included in any kk-factor of G′G'. In particular, the kk red edges between Nr(x)N_r(x) and xx are forced into every factor, giving xx its prescribed degree kk. Consequently, none of the newly added edges incident to xx can belong to any kk-factor. Thus the set of kk-factors of G′G' is identical to that of GG, which implies that the factor of G′G' is unique.

On the other hand, one can see that ∣E(G′)∣=∣E(G)∣+∣T0∣−k>∣E(G)∣|E(G')| = |E(G)| + |T_0| - k > |E(G)|, contradicting the assumption that GG is a maximum-size graph with a unique kk-factor. Therefore ∣T0∣=k|T_0| = k, completing the proof of the claim.

Since Nr(x)⊆T0N_r(x) \subseteq T_0 and both sets have size kk, we have T0=Nr(x)T_0 = N_r(x).

We assert that xx is a universal vertex of GG. Repeated applications of Lemma 2.3(ii) show that G−T0G - T_0 is extremal for the residual degree function

f0(v)=dF−T0(v)=k−∣Nr(v)∩T0∣,for v∈V(G)∖T0.f_0(v) = d_{F-T_0}(v) = k - |N_r(v) \cap T_0|,\qquad\text{for } v \in V(G) \setminus T_0.

Furthermore, xx is a free vertex in G−T0G - T_0. By Lemma 2.3(i), every free vertex in an extremal graph is universal, so xx is adjacent to all other vertices in G−T0G - T_0. Since xx is also adjacent to every vertex in T0T_0 (as T0=Nr(x)T_0 = N_r(x)), it follows that xx is adjacent to every other vertex in GG. Hence the assertion holds.

By the assertion of the universal vertex xx of GG, dG(x)=n−1>kd_G(x) = n - 1 > k, since k≤n−2k \le n - 2. For any other vertex y∉T0∪{x}y \notin T_0 \cup\{x\}, xyxy is blue because xx is universal and Nr(x)=T0N_r(x) = T_0. Together with the kk red edges incident to yy, this gives dG(y)≥k+1d_G(y) \ge k + 1. Thus, by Claim 3, D=T0=Nr(x)D = T_0 = N_r(x) and ∣D∣=k|D| = k.

The proof of Theorem 1.4 is complete.

References

  1. [1]S. Akbari, A. H. Ghodrati, and M. A. Hosseinzadeh, On the structure of graphs having a unique k-factor, Australas. J. Combin. 69 (2017), 63–73.
  2. [2]G. R. T. Hendry, Maximum graphs with a unique k-factor, J. Combin. Theory Ser. B 37 (1984), 53–63.DOI
  3. [3]A. Hoffmann and L. Volkmann, On unique k-factors and unique [1, k]-factors in graphs, Discrete Math. 278 (2004), 127–138.
  4. [4]A. Hoffmann and L. Volkmann, Structural remarks on bipartite graphs with unique f-factors, Graphs Combin. 21 (2005), 421–425.
  5. [5]A. Hoffmann, E. Sidorowicz, and L. Volkmann, Extremal bipartite graphs with a unique k-factor, Discuss. Math. Graph Theory 26 (2006), 181–192.
  6. [6]B. Jackson and R. W. Whitty, A note concerning graphs with unique f-factors, J. Graph Theory 13 (1989), 577–580.DOI
  7. [7]P. Johann, On the structure of graphs with a unique k-factor, J. Graph Theory 35 (2000), 227–243.DOI
  8. [8]L. Lovász, Subgraphs with prescribed valencies, J. Combinatorial Theory 8 (1970), 391–416.DOI
  9. [9]L. Lovász, On the structure of factorizable graphs I, Acta Math. Acad. Sci. Hungar. 23 (1972), 179–195.DOI
  10. [10]L. Volkmann, The maximum size of graphs with a unique k-factor, Combinatorica 24 (2004), 531–540.

Paper details

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

views · 8

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