betaFeedback

WorksComputer Science

Degree Realization with Maximum Matching

Abstract

The Maximum Matching Degree Realization problem requires, for a sequence dd of nn positive integers, to compute a realizing graph(whose degree sequence corresponds to dd) with the maximum possible matching. We present a polynomial-time algorithm for this problem. The decision version of this problem requires to determine whether a sequence dd admits a realization with a matching of size νν (without computing such a realization). Recently, it was shown that it can be done by verifying a series of inequalities. We improve the existing characterization by reducing the number of inequalities.

Introduction

The Degree Realization (DR) problem requires to decide, for a given non-increasing sequence d=(d1,…,dn)d=(d_1,\ldots,d_n) of positive integers, if there exists some nn-vertex (simple undirected) graph G=(V,E)G=(V,E) such that deg⁡G(i)=di\deg_G(i)=d_i for every i∈{1,…,n}i\in\{1,\ldots,n\}, and to construct such a graph if it exists. Such a sequence dd is called graphic.

Two central questions on realizations concern characterizations (i.e., necessary and sufficient conditions) for a sequence to be graphic, and efficient algorithms for finding realizing graphs. A necessary and sufficient condition for a given sequence of integers to be graphic (also implying an O(n)O(n) decision algorithm) was presented by Erdős and Gallai [7]. Havel [16] and Hakimi [15] described an O(∑idi)O(\sum_i d_i)-time algorithm that given a sequence dd of integers proves that the given sequence is not graphic or computes an mm-edge graph realizing it, where m=12∑i=1ndim=\frac{1}{2}\sum_{i=1}^{n}d_i.

Here, we study the variant of the problem where, given a sequence with possibly many realizing graphs, the goal is to find a realizing graph that also optimizes some quality measure. Hereafter, we refer to such problems as optimized realization problems. Concretely, we consider the classical Maximum Matching (MM) problem. For a graph G=(V,E)G=(V,E), a matching is an edge set M⊆EM\subseteq E, such that ee and e′e' do not share a vertex, for every two distinct e,e′∈Me,e'\in M. The size of the maximum matching in GG is denoted by

MM⁡(G)=max⁡{∣M∣∣M is a matching in G}.\operatorname{MM}(G)=\max\{|M|\mid M\text{ is a matching in }G\}.

Given a graphic sequence dd, we look for a realizing graph GG with the maximum possible matching. For example, for d=(2,2,2,2,2,2)d=(2,2,2,2,2,2), a realization G1G_1 consisting of a 6-vertex cycle is better that a realization G2G_2 consisting of two triangles, since MM⁡(G1)=3\operatorname{MM}(G_1)=3 whereas MM⁡(G2)=2\operatorname{MM}(G_2)=2. The resulting optimized realization problem is formally defined as follows. Letting

MM⁡(d)=max⁡{MM⁡(G)∣G is a realization of d},\operatorname{MM}(d)=\max\{\operatorname{MM}(G)\mid G\text{ is a realization of }d\},

the MM Degree Realization (MM-DR) problem requires finding a realizing graph GG attaining MM⁡(d)\operatorname{MM}(d).

Similarly, one may define optimized realization problems for other graph optimization problems, such as Maximum Clique, Maximum Independent Set, Minimum Vertex Cover, and Minimum Dominating Set. Their optimal values on a given graph GG are defined as MC⁡(G)\operatorname{MC}(G), MIS⁡(G)\operatorname{MIS}(G), MVC⁡(G)\operatorname{MVC}(G), and MDS⁡(G)\operatorname{MDS}(G), respectively. The corresponding optimized realization problems on degree sequences are named Maximum Clique Degree Realization (MC-DR), MIS Degree Realization (MIS-DR), MVC Degree Realization (MVC-DR), and MDS Degree Realization (MDS-DR), and their optimal values on a given dd are denoted by MC⁡(d)\operatorname{MC}(d), MIS⁡(d)\operatorname{MIS}(d), MVC⁡(d)\operatorname{MVC}(d), and MDS⁡(d)\operatorname{MDS}(d), respectively.

Interestingly, while the graph versions of most of these optimization problems are NP-hard, the optimized realization versions of MC, MIS, MVC, and MDS have been shown to be polynomial-time solvable. Rao [24] gave a characterization of sequences realizable by a graph containing a clique KℓK_\ell of size ℓ\ell. This result was based on a phenomenon known as the prefix lemma, which for MC says that if dd has a realization containing KℓK_\ell, then it has a realization such that the ℓ\ell vertices of maximum degree induce a clique KℓK_\ell. This result implies a polynomial-time algorithm for MC-DR (see, e.g., [13]). Consequently, it follows readily that polynomial-time algorithms also exist for MIS-DR and MVC-DR. Note that a prefix lemma also applies to MVC. This prefix property is satisfied by MDS [13], and it was recently used to obtain a characterization and a realization algorithm for MDS-DR [3].

As for MM-DR, the prefix property is satisfied also by MM [14]. Moreover, due to this property, MM(dd) can be computed efficiently using a result by Kundu [19] (see details below). However, so far it was not known how to exploit this property in order to derive a polynomial-time algorithm for MM-DR. This problem was handled for some restricted graph families in [5], but the general problem was left open.

Recently, Erdős et al. [9] studied MM-DR. Given a sequence dd and an integer ν\nu, they presented an Erdős–Gallai type characterization, based on a system of O(n)O(n) inequalities, which is satisfied if and only if dd has a realization with a matching of size ν\nu. Applying these characterizations to a given degree sequence, the maximum size of a matching can be computed efficiently, although a specific realization is not provided.

Our Results

Here, we present a polynomial-time realization algorithm for MM-DR. Our algorithm makes use of a stronger version of an existing prefix lemma for general graphs [14], termed the inverted prefix lemma, established in the current paper. This lemma is analogous to the inverted prefix lemma established in [5] for bipartite realizations of two sequences (or a bi-sequence). We also utilize an algorithm due to Fulkerson, Hoffman and McAndrew [11] for a special case of the ff-factor problem (discussed later), which is based on the following three phases:

  1. Realization of the bi-sequence (d,d)(d,d) by a bipartite graph G^\hat{G},

  1. Conversion of G^\hat{G} to a half-integral general (non-bipartite) realization GωG^\omega for dd, where in a half-integral realization an edge with weight half contributes half to the degree of its end-points.

  1. Rounding GωG^\omega to an integral general realization GG.

In addition, we show how the described method leads to the characterization recently proved by Erdős et al. [9]. In fact, we show that one of the equations in the characterization is redundant.

Related Work

Several papers studied network realization with a given subgraph. Kundu [19] showed that the sequences dd and the component-wise difference d−d′d-d', such that di′∈{k,k+1}d'_i \in\{k,k+1\} and d′≤dd' \le d (component-wise), are graphic only if there exists a graph GG realizing dd that has a subgraph G′G' realizing d′d'. This result can be used to decide whether MM(dd) ≥ℓ\ge\ell, for a given ℓ\ell, by checking d′=(12ℓ,0n−2ℓ)d'=(1^{2\ell},0^{n-2\ell}). Furthermore, MM(dd) can be computed efficiently, since MM(dd) is the maximum ℓ\ell, such that d−(12ℓ,0n−2ℓ)d-(1^{2\ell},0^{n-2\ell}) is realizable. This result can also be used to decide whether a given sequence dd has a perfect matching by assigning di′=1d'_i=1, for every ii. Kleitman and Wang [18] gave an algorithm for computing a realization of dd that contains a subgraph which realizes d′d'. Their algorithm can be used to compute a realization of dd that contains a perfect matching, if such a realization exists. Extensions of the above result were presented in [18, 21].

Rao and Rao [23] and Kundu [19] gave a characterization of sequences that can be realized by a Hamiltonian graph. Chungphaisan [6] gave an algorithm, that given a sequence dd, constructs a realization with a Hamiltonian cycle (or path), if such a realization exists. Rao [24] characterized sequences that can be realized by a graph containing KℓK_\ell (a clique of size ℓ\ell). This result was based on on the Prefix Lemma for MC. An alternative proof was given in [17], and a constructive proof was presented in [26]. It follows that MC-DR can be solved in polynomial time by checking if dd has a realization containing KℓK_\ell, for ℓ∈{2,…,n}\ell\in\{2,\ldots,n\}.

Gould, Jackson and Lehel [14] extended Rao’s result by showing that if dd has a realization containing HH as a subgraph (but not necessarily an induced sub-graph), then there exists a realization of dd containing HH where the vertices of HH have the ∣V(H)∣|V(H)| largest degrees. Yin [25] used this to extend Rao’s result [24] by giving a characterization of graphic sequences that contains a split graph Sr,sS_{r,s} composed of a clique is of size rr and an independent set of size ss. (Observe that Sr,1S_{r,1} is a clique of size r+1r+1.)

Gentner, Henning and Rautenbach [13] studied MIS-DR and MDS-DR. They proved the prefix lemma for MDS-DR and gave a realization algorithm for MDS-DR on sequences with d1=O(1)d_1=O(1), leaving the general case open. They also provided characterizations for MIS-DR and MDS-DR in forests. Gentner, Henning and Rautenbach [12] gave characterizations to realizations that minimize the maximum size of an independent set and that maximize the minimum size of a dominating set in forests. Recently, Bar-Noy et al. [3] gave a characterization and a realization algorithm for MDS-DR in general graphs.

Bock and Rautenbach [5] studied MM-DR in trees and bipartite graphs, where the partition is given. Their result on bipartite graphs is also based on a stronger version of the prefix lemma, which is essentially an inverted prefix lemma for bipartite graphs.

Fulkerson, Hoffman and McAndrew [11] provided a characterization for the realizability of a sequence dd with respect to multi-graphs that satisfy the odd cycle condition (discussed later). Building on the result of [11], Kundu [20] presented conditions for the factorization of graphs that satisfy the odd cycle condition. Anstee relied on the technique of [11] to obtain an algorithmic proof of the ff-factor theorem [1] and a simplified characterization for the existence of a (g,f)(g,f)-factor for special cases [2]. The result of Yin [25], mentioned above, was also based on [11]. The results for MDS-DR [3] are also based on this technique.

Inverted Prefix Lemma

In this section, we establish the inverted prefix lemma. Recall that Gould, Jacobson and Lehel [14] gave a general prefix lemma that applies to any subgraph. In the following lemma we provide the special case of a matching.

Lemma 2.1 (Arbitrary Prefix Lemma for MM [14]). If a sequence dd has a realization with a matching of size ν\nu, then dd has a realization with a matching of the same size such that 2ν2\nu vertices participating in the matching have the highest 2ν2\nu degrees in dd, i.e., d1,d2,…,d2νd_1,d_2,\ldots,d_{2\nu}.

For our purposes, however, we need a stronger type of prefix lemma, similar to the one used in [5] for solving MM-DR over bipartite graphs. Towards proving this stronger claim, we introduce some notation. Consider a realization G=(V,E)G=(V,E) of a degree sequence dd, with four vertices x,y,u,v∈Vx,y,u,v \in V such that (x,u),(y,v)∈E(x,u),(y,v) \in E and (x,y),(u,v)∉E(x,y),(u,v) \notin E. Then the FLIP operation transforms GG into a graph G′=(V,E′)G'=(V,E') by replacing the former two edges with the latter two, i.e., setting

E′=E∪{(x,y),(u,v)}∖{(x,u),(y,v)}.E' = E \cup\{(x,y),(u,v)\} \setminus\{(x,u),(y,v)\}.

This operation preserves the degrees of individual vertices, but could lead to non-isomorphic realization. It was widely studied and used in different contexts, see [10, 8, 4]. Finally, define [i,j]={i,…,j}[i,j]=\{i,\ldots,j\}, for i≤ji\le j and [i]=[1,i]={1,…,i}[i]=[1,i]=\{1,\ldots,i\} for an integer ii.

Lemma 2.2. Let G=(V,E)G=(V,E) be a realization of dd with V={v1,…,vn}V=\{v_1,\ldots,v_n\}, such that deg⁡G(vi)=di\deg_G(v_i)=d_i for every i∈[n]i\in[n]. If there is a matching M⊆EM\subseteq E covering the first 2ν2\nu vertices v1,…,v2νv_1,\ldots,v_{2\nu}, then there is a realization G′=(V,E′)G'=(V,E') of dd with the "inverted" matching

Minv={(vi,v2ν−i+1)∣i∈[ν]},M^{\mathrm{inv}}=\{(v_i,v_{2\nu-i+1})\mid i\in[\nu]\},

such that Minv⊆E′M^{\mathrm{inv}}\subseteq E'.

Proof. Call the pair (G,M)(G,M) valid if G=(V,E)G=(V,E) is defined on V={v1,…,vn}V=\{v_1,\ldots,v_n\} with deg⁡(vi)=di\deg(v_i)=d_i, M⊆EM\subseteq E, and MM is on {v1,v2,…,v2ν}\{v_1,v_2,\ldots,v_{2\nu}\}. Consider a valid pair (G,M)(G,M) and let

I(M)={i∣(vi,v2ν−i+1)∉M, i∈[ν]}I(M)=\{i\mid(v_i,v_{2\nu-i+1})\notin M,\ i\in[\nu]\}

and f(M)=min⁡I(M)f(M)=\min I(M). If I(M)=∅I(M)=\varnothing, then M=MinvM=M^{\mathrm{inv}}, and we are done.

We describe procedure Invert that given a valid pair (G,M)(G,M) violating the claim produces a new valid pair (G′,M′)(G',M'), such that either (G′,M′)(G',M') satisfies the claim or f(M′)>f(M)f(M')>f(M). Repeatedly applying Invert gradually modifies (G,M)(G,M) while preserving validity and strictly increasing f(M)f(M). Since ff is bounded above by ν\nu, the process terminates in at most ν\nu steps and the obtained pair (G′,M′)(G',M') satisfies the claim.

Given a pair (G,M)(G,M) not satisfying the claim, let i=f(M)i=f(M) and j=2ν−i+1j=2\nu-i+1. Since (vi,vj)∉M(v_i,v_j)\notin M, there are edges (vi,vx),(vy,vj)∈M(v_i,v_x),(v_y,v_j)\in M, and the involved vertices satisfy deg⁡G(vi)≥deg⁡G(vy)\deg_G(v_i)\ge\deg_G(v_y) and deg⁡G(vj)≤deg⁡G(vx)\deg_G(v_j)\le\deg_G(v_x) by the definition of ff. Let

M′=M∪{(vi,vj),(vx,vy)}∖{(vi,vx),(vy,vj)}.M'=M\cup\{(v_i,v_j),(v_x,v_y)\}\setminus\{(v_i,v_x),(v_y,v_j)\}.

If there is a realization G′G' such that M′⊆G′M'\subseteq G', then the pair (G′,M′)(G',M') is valid and either satisfies the claim or increases ff. Proceed according to one of the following cases to obtain G′G'. See Figure 1.

Figure 1. Illustration of the cases in the proof of Lemma 2.2. All the illustrating figures maintain the convention that solid lines represent edges existing in the graph and dashed lines represent edges not in the graph.

Case 1: (vi,vj),(vx,vy)∈E(G)(v_i,v_j),(v_x,v_y)\in E(G).

Then simply take G′=GG'=G.

Case 2: (vi,vj),(vx,vy)∉E(G)(v_i,v_j),(v_x,v_y)\notin E(G).

Then perform a FLIP operation on GG replacing (vi,vx),(vy,vj)(v_i,v_x),(v_y,v_j) with (vi,vj),(vx,vy)(v_i,v_j),(v_x,v_y). G′G' obtained in this way satisfies M′⊆E(G′)M'\subseteq E(G').

Case 3: (vi,vj)∈E(G)(v_i,v_j)\in E(G) and (vx,vy)∉E(G)(v_x,v_y)\notin E(G).

Then there is a vertex vz∈V(G)∖{vi,vj,vx,vy}v_z\in V(G)\setminus\{v_i,v_j,v_x,v_y\}, such that (vx,vz)∈E(G)(v_x,v_z)\in E(G) and (vj,vz)∉E(G)(v_j,v_z)\notin E(G). Indeed, deg⁡G(vx)≥deg⁡G(vj)\deg_G(v_x)\ge\deg_G(v_j) and vyv_y is connected to vjv_j, but not to vxv_x, so there exists vzv_z compensating for this. Obtain G′G' by doing a FLIP replacing (vx,vz),(vj,vy)(v_x,v_z),(v_j,v_y) with (vx,vy),(vj,vz)(v_x,v_y),(v_j,v_z).

Case 4: (vi,vj)∉E(G)(v_i,v_j)\notin E(G) and (vx,vy)∈E(G)(v_x,v_y)\in E(G).

Then there is a vertex vz∈V(G)∖{vi,vj,vx,vy}v_z\in V(G)\setminus\{v_i,v_j,v_x,v_y\}, such that (vi,vz)∈E(G)(v_i,v_z)\in E(G) and (vy,vz)∉E(G)(v_y,v_z)\notin E(G). Similarly to the previous case, this is because deg⁡G(vi)≥deg⁡G(vy)\deg_G(v_i)\ge\deg_G(v_y). Obtain G′G' by doing a FLIP replacing (vi,vz),(vj,vy)(v_i,v_z),(v_j,v_y) with (vi,vj),(vy,vz)(v_i,v_j),(v_y,v_z).

The lemma follows.

Combining Lemma 2.1 and Lemma 2.2 gives a more specific Prefix Lemma for Maximum Matching.

Lemma 2.3 (Inverted Prefix Lemma for MM). If a sequence dd has a realization G=(V,E)G=(V,E) where V={v1,…,vn}V=\{v_1,\ldots,v_n\} such that deg⁡G(vi)=di\deg_G(v_i)=d_i for every i∈[n]i\in[n], with a matching MM of size ν\nu, then dd has a realization G′=(V,E′)G'=(V,E') with the matching M′={(vi,v2ν−i+1)∣i∈[ν]}M'=\{(v_i,v_{2\nu-i+1})\mid i\in[\nu]\}.

Algorithm for Realization with Maximum Matching

Fulkerson, Hoffman and McAndrew [11] presented an algorithm for a special case of the ff-factor problem. More specifically, they considered the following degree realization problem. Let dd be a sequence, and let c∈(Z+)n×nc\in(\mathbb{Z}_+)^{n\times n} be a symmetric integral matrix. Intuitively, one can think of cc as representing a multigraph KcK_c over V={1,…,n}V=\{1,\ldots,n\} with ci,jc_{i,j} parallel edges between ii and jj for every 1≤i,j≤n1\leq i,j\leq n. Fulkerson et al. [11] studied the problem of finding a multigraph H=(V,E)H=(V,E), such that deg⁡H(i)=di\deg_H(i)=d_i and the number of parallel edges between ii and jj is bounded above by ci,jc_{i,j}. Intuitively, the sought realizing multigraph HH needs to be a sub-multigraph, or factor, of KcK_c. We refer to such a realization as a realization of dd with respect to cc.

Let Gc=(V,Ec)G_c=(V,E_c) be a graph derived from cc, where

Ec={(i,j)∣i,j∈V and ci,j>0}.E_c=\{(i,j)\mid i,j\in V\text{ and }c_{i,j}>0\}.

That is, GcG_c is obtained from KcK_c by replacing all multiedges by edges.

The matrix cc is said to satisfy the odd-cycle condition if and only if the distance between any two disjoint odd cycles in the derived graph GcG_c is at most one. In other words, any two disjoint odd cycles in GcG_c must be connected by an edge.

Fulkerson et al. [11] presented a characterization for the realizability of a sequence dd with respect to cc that satisfies the odd-cycle condition. Their proof is constructive in the sense that it implies a realization algorithm for instances, where cc satisfies the odd-cycle condition. The details of this algorithm for the specific context of realization with maximum matching are given in § 4.

Theorem 3.1 ([11]). Let dd be a sequence of size nn, and let c∈(Z+)n×nc \in(\mathbb{Z}_{+})^{n \times n} be a symmetric integral matrix. There exists a polynomial-time algorithm that computes a realization of dd with respect to cc or determine that there is no such realization, assuming that cc satisfies the odd-cycle condition.

We show that we can use Theorem 3.1 to obtain a realization algorithm for MM-DR with a matching of size ν=MM⁡(d)\nu= \operatorname{MM}(d).

Given a sequence dd, our first step is to compute MM⁡(d)\operatorname{MM}(d) using the Erdős-Gallai type characterization of Erdős et al. [9].

Next, Based on the Inverted Prefix Lemma (Lemma 2.3), we construct an instance d′d' and c′c' as follows:

di′={di−1i≤2ν,dii>2ν,andci,j′={0i=j,0i+j=2ν+1,1otherwise.d'_i = \begin{cases} d_i-1 & i \le2\nu,\\ d_i & i > 2\nu, \end{cases} \qquad\text{and}\qquad c'_{i,j} = \begin{cases} 0 & i=j,\\ 0 & i+j=2\nu+1,\\ 1 & \text{otherwise.} \end{cases}

Observation 3.2. There is a realization of dd with a matching of size ν\nu if and only if there is a realization of d′d' with respect to c′c'.

Observation 3.3 (Odd-cycle condition). c′c' satisfies the odd-cycle condition. That is, for any pair of disjoint odd cycles C1,C2C_1,C_2 in Gc′G_{c'}, there exist i∈C1i \in C_1 and j∈C2j \in C_2, such that (i,j)∈Ec′(i,j) \in E_{c'}.

Proof. Let i∈C1i \in C_1, j′∈C2j' \in C_2 be arbitrary vertices. If i+j′=2ν+1i+j'=2\nu+1, then let j≠j′j \ne j' be any other vertex in C2C_2. Otherwise, let j=j′j=j'.

This implies the following.

Theorem 3.4. There exists a polynomial-time algorithm for constructing a realization of a given graphic sequence dd that also has a matching of maximum size (among all possible realizations of dd).

Detailed Realization Algorithm

In this section we present the full details of the realization algorithm that was mentioned in the previous section. The algorithm proceeds in several steps, presented in the coming subsections. First, the algorithm computes ν=MM⁡(d)\nu= \operatorname{MM}(d) using the Arbitrary Prefix Lemma (Lemma 2.1) and Kundu’s result [19]. Next, the MM-DR problem over general graph is reduced to the same problem over bipartite graphs, by applying the realization algorithm of Fulkerson et al. [11] while ensuring preservation of a matching. Then, MM-DR over bipartite graphs is reduced to a maximum flow problem. To be more specific, given the size ν\nu of the maximum matching and a degree sequence pair (d,d)(d,d), we construct a bipartite flow graph Gd,νG_{d,\nu}, such that if the maximum flow attained in Gd,νG_{d,\nu} equals ∑i=1ndi−2ν\sum_{i=1}^{n} d_i - 2\nu, then it corresponds to a realization G^\widehat{G} of (d,d)(d,d) with a matching of size 2ν2\nu. (This is where we make use of the Inverted Prefix Lemma 2.3.) The next step is to convert G^\widehat{G} to a half integral general (non-bipartite) realization GwG^{w} for dd. Finally, GwG^{w} is rounded to an integral general realization GG.

Computation of MM (d)

As mentioned before, given a candidate value ν\nu, one can check whether MM⁡(d)≥ν\operatorname{MM}(d) \ge\nu by using the result of Kundu [19] with d′=(12ν,0n−2ν)d' = (1^{2\nu},0^{n-2\nu}). That can be done in O(n)O(n) time using [7]. Hence, MM⁡(d)\operatorname{MM}(d) can be computed in O(nlog⁡n)O(n \log n) time using binary search.

Reduction to a Bipartite Sequence Pair

Given a sequence dd, a bipartite graph G^=(V,W,E^)\hat{G} = (V,W,\hat{E}), where V={v1,…,vn}V = \{v_1,\ldots,v_n\} and W={w1,…,wn}W = \{w_1,\ldots,w_n\}, is a ν\nu-matched realization for the bi-sequence, (d,d)(d,d) if it satisfies the properties:

(M1) G^\hat{G} realizes the sequence pair (d,d)(d,d).

(M2) (vi,wi)∉E^(v_i,w_i) \notin\hat{E} for every i∈[n]i \in[n].

(M3) M^={(vi,w2ν−i+1)∣i∈[2ν]}⊆E^\hat{M} = \{(v_i,w_{2\nu-i+1}) \mid i \in[2\nu]\} \subseteq\hat{E}.

First, we describe an algorithm that given a ν\nu-matched realization G^\hat{G} of (d,d)(d,d), produces a graph GG realizing dd with a matching of size ν\nu.

  1. Compute a half-integral solution.

    (a) For all i,j∈[n]i,j \in[n], let

yij={1,{vi,wj}∈E^,0,otherwise,andω(i,j)=12(yij+yji).y_{ij} = \begin{cases} 1, & \{v_i,w_j\} \in\hat{E},\\ 0, & \text{otherwise}, \end{cases} \qquad\text{and}\qquad \omega(i,j) = \frac{1}{2}(y_{ij}+y_{ji}).

(b) Define a weighted graph Gω=(Vω,Eω,ω)G^\omega= (V^\omega,E^\omega,\omega) with vertex set Vω=[n]V^\omega= [n] and an edge e=(i,j)e=(i,j) of weight ω(e)=ω(i,j)\omega(e)=\omega(i,j) for every i,j∈Vωi,j \in V^\omega. Clearly, ω\omega is half-integral.

(c) Let Mω={(i,2ν−i+1)∣i∈[ν]}M^\omega= \{(i,2\nu-i+1) \mid i \in[\nu]\} be the inverted matching in GωG^\omega. According to (M3)

ω(e)=1,for every e∈Mω.(1)\omega(e)=1,\quad\text{for every }e\in M^\omega. \tag*{(1)}

(d) Define the weighted degree of a vertex i∈Vωi \in V^\omega to be

dω(i)=∑j∈Vωω(i,j).d^\omega(i)=\sum_{j\in V^\omega}\omega(i,j).

Note that GωG^\omega realizes dd in the weighted sense, namely,

dω(i)=∑j∈Vωω(i,j)=12(∑j=1nyij+∑j=1nyji)=di,for any i∈Vω.d^\omega(i)=\sum_{j\in V^\omega}\omega(i,j) =\frac{1}{2}\left(\sum_{j=1}^{n}y_{ij}+\sum_{j=1}^{n}y_{ji}\right) =d_i,\qquad\text{for any }i\in V^\omega.
  1. Preparing for discarding non-integral weights while keeping the degrees unchanged. Construct a graph G1/2=(V1/2,E1/2)G^{1/2}=(V^{1/2},E^{1/2}) obtained by removing from GωG^\omega the edges of integral weight and keeping only those of weight 1/21/2. Formally, V1/2=VωV^{1/2}=V^\omega and E1/2={e∈Eω∣ω(e)=1/2}E^{1/2}=\{e\in E^\omega\mid\omega(e)=1/2\}.

In later stages of the construction, whenever GωG^\omega is modified (by changing the weight of some edge ee from 1/21/2 to 0 or 1), G1/2G^{1/2} is modified accordingly (by removing the edge ee).

  1. Partition into cycles.

(a) Partition the edge set of G1/2G^{1/2} into disjoint (not necessarily simple) cycles each covering an entire connected component of the graph. Since G1/2G^{1/2} is an even graph by Observation 4.1, this can be done in polynomial number of steps.

(b) Let C\mathcal{C} be a set of cycles in the partition.

(c) Let Ceven←{C∈C∣C is of even length}\mathcal{C}^{\mathrm{even}} \leftarrow\{C \in\mathcal{C} \mid C\text{ is of even length}\}, Codd←C∖Ceven\mathcal{C}^{\mathrm{odd}} \leftarrow\mathcal{C} \setminus\mathcal{C}^{\mathrm{even}}.

  1. Eliminate even cycles.

For every cycle C∈CevenC \in\mathcal{C}^{\mathrm{even}}, do the following.

(a) Traverse CC starting from an arbitrary vertex x∈Cx \in C and continuing along the cycle until returning to xx. Denote the resulting sequence of edges by E(C)=(e1,e2,…,eℓ)E(C) = (e_1,e_2,\ldots,e_\ell).

(b) Increase (resp., decrease) edge weights on even (resp., odd) positions in the sequence E(C)E(C) by 1/21/2. That is, for every i∈[ℓ]i \in[\ell], ω(ei)\omega(e_i) is set to 11 if ii is even and 00 otherwise. (This does not change the weighted degrees in GωG^\omega and does not affect other cycles in C\mathcal{C} or edges in MωM^\omega.)

  1. Eliminate odd cycles.

Arrange the cycles in Codd\mathcal{C}^{\mathrm{odd}} in pairs (by Observation 4.2 their number is even). For every pair of cycles (C,C′)(C,C') choose vertices x∈Cx \in C, y∈C′y \in C' according to Observation 4.3. Then do the following.

(a) Starting from x∈Cx \in C, traverse CC via edges E(C)=(e1,e2,…,eℓ)E(C) = (e_1,e_2,\ldots,e_\ell). Starting from vertex y∈C′y \in C', traverse C′C' via edges E(C′)=(e1′,…,ek′)E(C') = (e'_1,\ldots,e'_k).

(b) Let ξ=ω(x,y)\xi= \omega(x,y) (by Observation 4.3, this weight must be either 00 or 11).

(c) Set ω(x,y)←1−ξ\omega(x,y) \leftarrow1-\xi.

(d) For every i∈[ℓ]i \in[\ell] and j∈[k]j \in[k], modify the edge weights in the cycles CC and C′C' as follows:

ω(ei)←{1−ξ,i is even,ξ,i is odd,ω(ej′)←{1−ξ,j is even,ξ,j is odd.\omega(e_i) \leftarrow \begin{cases} 1-\xi, & i\text{ is even},\\ \xi, & i\text{ is odd}, \end{cases} \qquad \omega(e'_j) \leftarrow \begin{cases} 1-\xi, & j\text{ is even},\\ \xi, & j\text{ is odd}. \end{cases}

By Observation 4.4, at this stage each edge in GωG^\omega has weight 11 or 00, GωG^\omega realizes dd, and (1) holds.

  1. Generate the output GG.

Transform GωG^\omega into a simple graph GG, with an edge (i,j)(i,j) whenever ω(i,j)=1\omega(i,j)=1 in GωG^\omega. Note that M=MωM=M^\omega forms a matching in GG by (1).

The algorithm is justified by the following Observations.

Observation 4.1. The graph G1/2G^{1/2} is even (i.e., all its vertex degrees are even).

A connected even graph has an Euler cycle, implying the following.

Observation 4.2. The number of cycles in Codd\mathcal{C}^{\mathrm{odd}} is even.

Proof. Observe that ∑e∈Eωω(e)=12∑i=1ndi=m\sum_{e\in E^\omega}\omega(e)=\frac{1}{2}\sum_{i=1}^{n}d_i=m, where mm is the number of edges, which is an integer. Therefore, the number of edges with weight 1/21/2 must be even. Since the cycles in C\mathcal{C} cover all of E1/2E^{1/2} and are disjoint, the observation follows.

The following observation is implied by Observation 3.3.

Observation 4.3. For any pair of disjoint odd cycles C,C′∈CoddC,C'\in\mathcal{C}^{odd}, there exist x∈Cx\in C and y∈C′y\in C', such that (x,y)∉Mω(x,y)\notin M^\omega and ω(x,y)≠1/2\omega(x,y)\ne1/2.

Proof. Observation 3.3 implies that for any pair of disjoint odd cycles C,C′∈CoddC,C'\in\mathcal{C}^{odd}, there exist x∈Cx\in C and y∈C′y\in C', such that (x,y)∉Mω(x,y)\notin M^\omega.

Assume, towards contradiction, that ω(x,y)=1/2\omega(x,y)=1/2. Then the edge (x,y)(x,y) belongs to G1/2G^{1/2}, implying that xx and yy belong to the same connected component in G1/2G^{1/2}. But this contradicts the fact that x∈Cx\in C and y∈C′y\in C' where CC and C′C' cover different connected components of G1/2G^{1/2}.

Observation 4.4. At the end of Step 5, each edge in GωG^\omega has weight 1 or 0, GωG^\omega realizes dd and Eq. (1) holds.

Proof. After Step 5, GωG^\omega contains no more edges of weight 1/21/2. Moreover, neither of the modifications performed in Step 5 change the weighted degrees in GωG^\omega, affect other cycles in C\mathcal{C} or edges in MωM^\omega. The observation follows.

The reduction correctness follows from the next lemma.

Lemma 4.5. There exists a ν\nu-matched realization of the bi-sequence (d,d)(d,d) if and only if MM(d)≥νMM(d)\ge\nu.

Proof. If there is a ν\nu-matched realization of (d,d)(d,d), then the aforementioned algorithm produces a realization of dd with a matching of size ν\nu.

For the other direction, given a realization G=(V,E)G=(V,E) of dd with vertices V=[n]V=[n] and a matching M⊆EM\subseteq E of size ν\nu, there is a realization G′=(V,E′)G'=(V,E') with a matching M′={(vi,v2ν−i+1)∣i∈[ν]}M'=\{(v_i,v_{2\nu-i+1})\mid i\in[\nu]\} by the Inverted Prefix Lemma (Lemma 2.3). Consider the following graph G^=(V^,W^,E^)\widehat{G}=(\widehat{V},\widehat{W},\widehat{E}) with V^={v1,…,vn}\widehat{V}=\{v_1,\ldots,v_n\}, W^={w1,…,wn}\widehat{W}=\{w_1,\ldots,w_n\} and (vi,wj)∈E^(v_i,w_j)\in\widehat{E} if and only if (i,j)∈E′(i,j)\in E'. Clearly, G^\widehat{G} realizes (d,d)(d,d) and (vi,wi)∉E^(v_i,w_i)\notin\widehat{E} for every i∈[n]i\in[n], so it satisfies (M1) and (M2). Moreover, the set M^={(vi,wj)∣(i,j)∈M′}\widehat{M}=\{(v_i,w_j)\mid(i,j)\in M'\} is a matching of size 2ν2\nu in G^\widehat{G} satisfying (M3). Indeed, since M′M' is a matching, the edges in M^\widehat{M} form a matching too and each edge (i,j)∈M′(i,j)\in M' leads to two edges (vi,wj),(vj,wi)∈M^(v_i,w_j),(v_j,w_i)\in\widehat{M}. The lemma follows.

Reduction to Flow

According to the previous section (in particular, Lemma 4.5) given a degree sequence dd all we need is to find a bipartite ν\nu-matched realization of (d,d)(d,d) for maximum possible ν\nu. Next we describe how to construct a flow graph Gd,νG_{d,\nu} for any ν\nu, such that ν\nu-matched realization of (d,d)(d,d) exist if and only if the maximum flow in Gd,νG_{d,\nu} is ∑i=1ndi−2ν\sum_{i=1}^{n}d_i-2\nu. Moreover, given an integer flow of this value we describe how to construct a desired realization.

First we describe the construction of Gd,νG_{d,\nu}. The node set XX contains nodes xix_i (for i∈[n]i\in[n]), corresponding to the vertices of VV, and the source ss is connected to them. Similarly, the node set YY contains nodes yjy_j (for j∈[n]j\in[n]), corresponding to the vertices in WW, and these are connected to the sink tt. The nodes are organized into the following sets:

  • Candidates for the matching:

    XM={xi∣i∈[1,2ν]}X_M = \{x_i \mid i \in[1, 2\nu]\} and YM={yj∣j∈[1,2ν]}Y_M = \{y_j \mid j \in[1, 2\nu]\},

  • Rest of the nodes:

    XR={xi∣i∈[2ν+1,n]}X_R = \{x_i \mid i \in[2\nu+ 1, n]\} and YR={yj∣j∈[2ν+1,n]}Y_R = \{y_j \mid j \in[2\nu+ 1, n]\},

  • Source and sink: {s,t}\{s,t\}.

The edges are capacitated and directed from left to right, i.e., an edge (α,β,γ)(\alpha, \beta, \gamma) leads from the node α\alpha to the node β\beta and can carry up to γ\gamma units of flow. The source ss has edges leading to every node xix_i, with capacity di−1d_i - 1 for xi∈XMx_i \in X_M and did_i for xi∈XRx_i \in X_R. Similarly, there are edges leading from every node yjy_j to the sink tt, with capacity dj−1d_j - 1 for yj∈YMy_j \in Y_M and djd_j for yj∈YRy_j \in Y_R. This enforces the degree constraint for the vertices viv_i and wiw_i in GG. Finally, there’s a unit capacity edge (xi,yj,1)(x_i, y_j, 1) for every i,j∈[n]i,j \in[n], such that i≠ji \ne j and j≠2ν−i+1j \ne2\nu- i + 1. Overall, the edge set E~\widetilde{E} of the flow graph is structured as a complete (X,Y)(X,Y) biclique minus an inverted matching and minus diagonal edges, with a source ss connected to XX and a sink tt connected to YY. Formally, E~\widetilde{E} (along with the edge weights) is defined as follows:

E~={(s,xi,di−1)∣i∈[1,2ν]}∪{(s,xi,di)∣i∈[2ν+1,n]}∪{(xi,yj,1)∣i,j∈[1,n], i≠j, j≠2ν−i+1}∪{(yj,t,dj−1)∣j∈[1,2ν]}∪{(yj,t,dj)∣j∈[2ν+1,n]}.\begin{aligned} \widetilde{E} ={}& \{(s,x_i,d_i-1) \mid i \in[1,2\nu]\} \cup\{(s,x_i,d_i) \mid i \in[2\nu+1,n]\}\\ &{}\cup\{(x_i,y_j,1) \mid i,j \in[1,n],\ i \ne j,\ j \ne2\nu-i+1\}\\ &{}\cup\{(y_j,t,d_j-1) \mid j \in[1,2\nu]\} \cup\{(y_j,t,d_j) \mid j \in[2\nu+1,n]\}. \end{aligned}

The network Gd,νG_{d,\nu} is schematically depictured in Figure 2, dashed edges indicate forbidden matching and forbidden diagonal edges. The construction is justified by the following Lemma 4.6.

The flow network $G_{d,\nu}$

Figure 2. The flow network Gd,νG_{d,\nu}. Solid arcs are labeled by their capacities. Dashed lines indicate forbidden pairs. The middle arcs xi→yjx_i \to y_j, present exactly when i≠ji \ne j and i+j≠2ν+1i+j \ne2\nu+1, all have capacity 1 and are omitted for clarity.

Lemma 4.6. There exists a ν\nu-matched bipartite graph G^=(V,W,E^)\widehat{G} = (V, W, \widehat{E}) that realizes the (d,d)(d,d) if and only if the value of a maximum s−ts-t flow in Gd,νG_{d,\nu} is equal to ∑i=1ndi−2ν\sum_{i=1}^{n} d_i - 2\nu.

Proof. Suppose the maximum value of an s−ts-t flow in Gd,νG_{d,\nu} is ∑i=1ndi−2ν\sum_{i=1}^{n} d_i - 2\nu. Using integral flow theorem, we assume that the maximum flow is integral. Denote a value of the flow from a vertex xx to a vertex yy by flow⁡(x,y)\operatorname{flow}(x,y). Define the bipartite graph G^=(V,W,E^)\widehat{G} = (V, W, \widehat{E}) as follows:

  1. For each node xi∈Xx_i \in X, create a corresponding node vi∈Vv_i \in V.

  2. For each node yj∈Yy_j \in Y, create a corresponding node wj∈Ww_j \in W.

  3. For every 1≤i,j≤n1 \le i,j \le n, if flow⁡(xi,yj)=1\operatorname{flow}(x_i,y_j) = 1, then create an edge (vi,wj)(v_i,w_j) and add it to E^\widehat{E}.

  4. For every 1≤i≤2ν1 \le i \le2\nu create an edge (vi,w2ν−i+1)(v_i,w_{2\nu-i+1}) and add it to E^\widehat{E}.

It remains to verify that G^\widehat{G} correctly realizes (d,d)(d,d) and is ν\nu-matched. The degree of viv_i in G^\widehat{G} equals to the number of edges (xi,yj)(x_i,y_j) that carry flow if i∈[2ν+1,n]i \in[2\nu+1,n] and one more than the corresponding flow if i∈[2ν]i \in[2\nu]. Since xix_i conserves flow, and since all the edges (s,xi)(s,x_i) are saturated, deg⁡(vi)=di\deg(v_i) = d_i. Similarly, deg⁡(wj)=dj\deg(w_j) = d_j for every j∈[n]j \in[n], so G^\widehat{G} satisfies (M1). Since Gd,νG_{d,\nu} does not have edges (xi,yi)(x_i,y_i) for any i∈[n]i \in[n], it follows that G^\widehat{G} does not have edges (vi,wi)(v_i,w_i), satisfying (M2). Finally, the matching M^={(vi,w2ν−i+1)∣1≤i≤2ν}\widehat{M} = \{(v_i,w_{2\nu-i+1}) \mid1 \le i \le2\nu\} was added in step 4, so G^\widehat{G} satisfies (M3).

Conversely, suppose G^=(V,W,E^)\widehat{G}=(V,W,\widehat{E}), where V={v1,…,vn}V=\{v_1,\ldots,v_n\} and W={w1,…,wn}W=\{w_1,\ldots,w_n\}, is a ν\nu-matched bipartite graph realizing (d,d)(d,d) with the matching M^={(vi,w2ν−i+1)∣1≤i≤2ν}\widehat{M}=\{(v_i,w_{2\nu-i+1})\mid1\le i\le2\nu\}. We need to define a flow function on Gd,νG_{d,\nu} and prove that its value equals ∑i=1ndi−2ν\sum_{i=1}^{n}d_i-2\nu. Since the sum of capacities of outgoing edges from ss is exactly this sum, maximum flow cannot exceed it, thus it is enough to construct a flow with the aforementioned value.

  1. Saturate Edges from Source and to Sink:

flow⁡(s,xi)←{di−1i∈[1,2ν],dii∈[2ν+1,n],flow⁡(yj,t)←{dj−1j∈[1,2ν],djj∈[2ν+1,n].\begin{aligned} \operatorname{flow}(s,x_i)&\leftarrow \begin{cases} d_i-1 & i\in[1,2\nu],\\ d_i & i\in[2\nu+1,n], \end{cases} & \operatorname{flow}(y_j,t)&\leftarrow \begin{cases} d_j-1 & j\in[1,2\nu],\\ d_j & j\in[2\nu+1,n]. \end{cases} \end{aligned}
  1. Flow Through Edges:

For every i∈[n]i\in[n] and j∈[n]j\in[n] such that (vi,wj)∈E^∖M^(v_i,w_j)\in\widehat{E}\setminus\widehat{M}, set flow⁡(xi,yj)←1\operatorname{flow}(x_i,y_j)\leftarrow1,

  1. Completing the flow function:

Set the flows of all other edges to 0.

We need to argue that the defined flow is legal. Note that by construction, the total flow out of the source ss is ∑i=1ndi−2ν\sum_{i=1}^{n}d_i-2\nu and the total flow into the sink tt is ∑j=1ndj−2ν\sum_{j=1}^{n}d_j-2\nu. It remains to verify that for every vertex except ss and tt, the incoming and outgoing flows are equal.

  • Node xix_i: By construction, the incoming flow at xix_i is flow⁡(s,xi)=di−1\operatorname{flow}(s,x_i)=d_i-1 if xi∈XMx_i\in X_M and flow⁡(s,xi)=di\operatorname{flow}(s,x_i)=d_i if xi∈XRx_i\in X_R. As for the outgoing flow, recall that there are exactly di−1d_i-1 indices jj for which (vi,wj)∈E^∖M^(v_i,w_j)\in\widehat{E}\setminus\widehat{M} if i∈[2ν]i\in[2\nu] and did_i such indices if i∈[2ν+1,n]i\in[2\nu+1,n]. Hence, xix_i conserves flow.

  • Node yjy_j: By construction, the outgoing flow at yjy_j is flow⁡(yj,t)=dj−1\operatorname{flow}(y_j,t)=d_j-1 if xj∈XMx_j\in X_M and flow⁡(yj,t)=dj\operatorname{flow}(y_j,t)=d_j if yj∈YRy_j\in Y_R. As for the incoming flow, recall that there are exactly dj−1d_j-1 indices ii for which (vi,wj)∈E^∖M^(v_i,w_j)\in\widehat{E}\setminus\widehat{M} if j∈[2ν]j\in[2\nu] and djd_j such indices if j∈[2ν+1,n]j\in[2\nu+1,n]. Hence, yjy_j conserves flow.

The claim follows.

We conclude the section with the following result.

Theorem 4.7. There exists an O(n3)O(n^3) time algorithm for constructing a realization of a given graphic sequence dd that also has a matching of maximum size (among all possible realizations of dd).

Proof. As was shown in the beginning of this section a maximum size of a matching ν\nu can be found in a running time of O(nlog⁡n)O(n\log n). As for the realization algorithm, given ν\nu, to find a ν\nu-matched realization of dd we first build the flow graph Gd,νG_{d,\nu} and find a maximum ss-tt flow in it. Since Gd,νG_{d,\nu} has O(n)O(n) vertices and O(n2)O(n^2) edges, a maximum flow can be computed in O(n3)O(n^3) time using the maximum flow algorithm by Orlin [22]. Given a maximum flow, adjacency matrix for ν\nu-matched bipartite realization G^\widehat{G} for the sequence pair (d,d)(d,d) can be computed in O(n2)O(n^2) time. Next we go through all the steps of transformation of G^\widehat{G} into ν\nu-matched realization GG for dd and show that each step takes O(n3)O(n^3) time.

Step 1: The adjacency matrix of the weighted graph GωG^\omega can be computed from the adjacency matrix of G^\widehat{G} in O(n2)O(n^2).

Step 2: It takes O(n2)O(n^2) to compute the adjacency matrix of G1/2G^{1/2} using the adjacency matrix of GωG^\omega.

Step 3: Since an Eulerian cycle can be found by linear time in the number of edges and G1/2G^{1/2} is an even graph, a partition of G1/2G^{1/2} into disjoint cycles C\mathcal{C} takes O(n2)O(n^2) time.

Step 4: Separating even cycles in C\mathcal{C} and applying the corresponding modification to them takes O(n2)O(n^2) time.

Step 5: For every pair of odd cycles (C,C′)(C,C') it takes constant time to find vertices x∈Cx\in C and y∈C′y\in C' satisfying Observation 4.3 following the proof of Observation 3.3. Given xx and yy it takes linear time O(∣C∣+∣C′∣)O(|C|+|C'|) to apply corresponding modifications. Therefore, the complexity for all pairs of cycles is O(n2)O(n^2).

Step 6: At this step GωG^\omega does not have edges of weight 1/21/2, so it can be transformed into GG in O(n2)O(n^2) time.

The theorem follows.

Characterization

This section considers the characterization of MM⁡(d)\operatorname{MM}(d) of a given sequence dd. A characterization for this problem was recently given by Erdős et al. [9] and contains O(n)O(n) inequalities (see Theorem 5.1). In previous Sections the realization problem was reduced to a flow problem using the method developed by Fulkerson et al. [11]. We show that this technique not only leads to constructive algorithm, but also to an alternative proof of the characterization and show that one of its inequalities is redundant.

Theorem 5.1 (Theorem 2.13, [9]). For a graphic positive non-increasing degree sequence d=(d1,…,dn)d=(d_1,\ldots,d_n) and an integer ν\nu let

td(ν)=∣{i>2ν∣di=d2ν}∣−∣{i<2ν∣di=d2ν}∣,t_d(\nu)=\lvert\{i>2\nu\mid d_i=d_{2\nu}\}\rvert-\lvert\{i<2\nu\mid d_i=d_{2\nu}\}\rvert,
di′={di−1i≤2ν,dii>2ν.d_i'=\begin{cases}d_i-1 & i\le2\nu,\\ d_i & i>2\nu.\end{cases}

There exists a realization of dd with a matching of size ν\nu if and only if:

∑i=1kdi≤k2+∑i=k+1nmin⁡(di′,k),1≤k<ν,\sum_{i=1}^{k}d_i\le k^2+\sum_{i=k+1}^{n}\min(d_i',k),\qquad1\le k<\nu,
∑i=1kdi+∣{i>2ν∣di=d2ν}∣≤k2+∑i=k+1nmin⁡(di−Idi=d2ν,k),k=2ν+td(ν).\sum_{i=1}^{k}d_i+\lvert\{i>2\nu\mid d_i=d_{2\nu}\}\rvert\le k^2+\sum_{i=k+1}^{n}\min(d_i-\mathbb{I}_{d_i=d_{2\nu}},k),\qquad k=2\nu+t_d(\nu).

For a degree sequence dd, Lemmas 4.5 and 4.6 imply that MM⁡(d)≥ν\operatorname{MM}(d)\ge\nu if and only if the maximum ss-tt flow in Gd,νG_{d,\nu} has value ∑i=1ndi−2ν\sum_{i=1}^{n}d_i-2\nu. Let c(S,T)c(S,T) denote the capacity of an ss-tt cut (S,T)(S,T) in this network. The total capacity leaving ss is ∑i=1ndi−2ν\sum_{i=1}^{n}d_i-2\nu. Hence, by the max-flow min-cut theorem, the required flow exists if and only if c(S,T)≥∑i=1ndi−2νc(S,T)\ge\sum_{i=1}^{n}d_i-2\nu for every ss-tt cut. We show that these cut constraints reduce to the first family of inequalities in Theorem 5.1. Thus, the additional inequality in that characterization is redundant.

Theorem 5.2. Let dd be a graphic sequence, and let ν∈[⌊n/2⌋]\nu\in[\lfloor n/2\rfloor]. Define di′=di−1d_i'=d_i-1 for i∈[2ν]i\in[2\nu] and di′=did_i'=d_i for i∈[2ν+1,n].i\in[2\nu+1,n]. There exists a realization of dd with a matching of size ν\nu if and only if

∑i=1kdi≤k2+∑i=k+1nmin⁡(di′,k),1≤k<ν.(2)\sum_{i=1}^{k}d_i\le k^2+\sum_{i=k+1}^{n}\min(d_i',k),\qquad1\le k<\nu. \tag*{(2)}

The case ν=0\nu=0 is immediate. Throughout the proof, dd, ν\nu, and d′d' satisfy the assumptions and definitions of Theorem 5.2, and an interval with no indices denotes the empty set. We first rewrite the cut constraints and then reduce the number of inequalities that must be checked. For an ss-tt cut (S,T)(S,T), define the index sets

A={i∈[n]∣xi∈S}andB={j∈[n]∣yj∈S}.A=\{i\in[n]\mid x_i\in S\}\qquad\text{and}\qquad B=\{j\in[n]\mid y_j\in S\}.

These sets determine the cut: S={s}∪{xi∣i∈A}∪{yj∣j∈B}S=\{s\}\cup\{x_i\mid i\in A\}\cup\{y_j\mid j\in B\}, and TT is its complement. Summing the capacities of the edges from SS to TT gives the following lemma.

Lemma 5.3. Every ss-tt cut (S,T)(S,T) in Gd,νG_{d,\nu} satisfies c(S,T)≥∑i=1ndi−2νc(S,T)\ge\sum_{i=1}^{n}d_i-2\nu if and only if

∑i∈[n]∖Adi′+∑j∈Bdj′+e(A,[n]∖B)≥∑i=1ndi−2ν,∀A,B⊆[n].(3)\sum_{i\in[n]\setminus A}d_i'+\sum_{j\in B}d_j'+e(A,[n]\setminus B)\ge\sum_{i=1}^{n}d_i-2\nu,\qquad\forall A,B\subseteq[n]. \tag*{(3)}

where e(Q,R)e(Q,R) denotes the number of edges from {xi∣i∈Q}\{x_i\mid i\in Q\} to {yj∣j∈R}\{y_j\mid j\in R\} in Gd,νG_{d,\nu}.

For each fixed AA, we next minimize over BB to obtain a single inequality.

Lemma 5.4. Inequalities (3) hold if and only if

∑i∈Adi≤∣A∣(∣A∣−1)+∑j∈[n]∖Amin⁡(∣A∣,dj)−∣{i∈[2ν]∣i∉A, 2ν+1−i∉A, di≤∣A∣}∣,\sum_{i\in A} d_i \le|A|(|A|-1) + \sum_{j\in[n]\setminus A} \min(|A|,d_j) - |\{i\in[2\nu]\mid i\notin A,\ 2\nu+1-i\notin A,\ d_i\le|A|\}|,

for every A⊆[n]A\subseteq[n].

Proof. Since ∑i=1ndi′=∑i=1ndi−2ν\sum_{i=1}^{n}d'_i=\sum_{i=1}^{n}d_i-2\nu and ∑i∈Adi′+∑i∈[n]∖Adi′=∑i=1ndi′\sum_{i\in A}d'_i+\sum_{i\in[n]\setminus A}d'_i=\sum_{i=1}^{n}d'_i, rearranging (3) gives

∑i∈Adi′−∑j∈Bdj′≤e(A,[n]∖B),∀A,B⊆[n].\sum_{i\in A}d'_i-\sum_{j\in B}d'_j\le e(A,[n]\setminus B),\qquad\forall A,B\subseteq[n].

We first show that it suffices to consider disjoint sets AA and BB. For arbitrary A,B⊆[n]A,B\subseteq[n], let A′=A∖BA'=A\setminus B and B′=B∖AB'=B\setminus A. Then A′∩B′=∅A'\cap B'=\varnothing and ∑i∈A′di′−∑j∈B′dj′=∑i∈Adi′−∑j∈Bdj′\sum_{i\in A'}d'_i-\sum_{j\in B'}d'_j=\sum_{i\in A}d'_i-\sum_{j\in B}d'_j. Moreover,

e(A′,[n]∖B′)=e(A,[n]∖B)−e(A∩B,[n]∖B)+e(A′,A∩B)=e(A,[n]∖B)−e(A∩B,[n]∖B)+e(A∩B,A′)=e(A,[n]∖B)−e(A∩B,[n]∖(B∪A′))≤e(A,[n]∖B).(4)\begin{aligned} e(A',[n]\setminus B')&=e(A,[n]\setminus B)-e(A\cap B,[n]\setminus B)+e(A',A\cap B)\\ &=e(A,[n]\setminus B)-e(A\cap B,[n]\setminus B)+e(A\cap B,A')\\ &=e(A,[n]\setminus B)-e(A\cap B,[n]\setminus(B\cup A'))\\ &\le e(A,[n]\setminus B). \tag*{(4)} \end{aligned}

where the second equality uses the symmetry e(Q,R)=e(R,Q)e(Q,R)=e(R,Q) of the allowed pairs in Gd,νG_{d,\nu} and the third uses the fact that A′∩B=∅A'\cap B=\varnothing. Thus, (3) holds for all A,BA,B if and only if

∑i∈Adi′−∑j∈Bdj′≤e(A,[n]∖B),∀A,B⊆[n] such that A∩B=∅.\sum_{i\in A}d'_i-\sum_{j\in B}d'_j\le e(A,[n]\setminus B),\qquad\forall A,B\subseteq[n]\text{ such that }A\cap B=\varnothing.

For disjoint A,B⊆[n]A,B\subseteq[n], the definition of Gd,νG_{d,\nu} gives

e(A,[n]∖B)=∣A∣(n−1−∣B∣)−∣{i∈[2ν]∣i∈A and 2ν+1−i∈[n]∖B}∣=∣A∣(n−1−∣B∣)−∣A∩[2ν]∣+∣{i∈[2ν]∣i∈A and 2ν+1−i∈B}∣=∣A∣(n−1−∣B∣)−∣A∩[2ν]∣+∣{i∈[2ν]∣i∈B and 2ν+1−i∈A}∣.\begin{aligned} e(A,[n]\setminus B)&=|A|(n-1-|B|)-|\{i\in[2\nu]\mid i\in A\text{ and }2\nu+1-i\in[n]\setminus B\}|\\ &=|A|(n-1-|B|)-|A\cap[2\nu]|+|\{i\in[2\nu]\mid i\in A\text{ and }2\nu+1-i\in B\}|\\ &=|A|(n-1-|B|)-|A\cap[2\nu]|+|\{i\in[2\nu]\mid i\in B\text{ and }2\nu+1-i\in A\}|. \end{aligned}

Substituting this identity and the definition of d′d' into the preceding cut inequality yields

∑i∈Adi−∣A∩[2ν]∣−∑j∈Bdj+∣B∩[2ν]∣≤∣A∣(n−1−∣B∣)−∣A∩[2ν]∣+∣{i∈[2ν]∣i∈B and 2ν+1−i∈A}∣.\sum_{i\in A}d_i-|A\cap[2\nu]|-\sum_{j\in B}d_j+|B\cap[2\nu]|\le|A|(n-1-|B|)-|A\cap[2\nu]|+|\{i\in[2\nu]\mid i\in B\text{ and }2\nu+1-i\in A\}|.

Equivalently,

∑i∈Adi≤∣A∣(n−1)+∑j∈Bdj−∣A∣∣B∣−∣{j∈[2ν]∣j∈B and 2ν+1−j∉A}∣.\sum_{i\in A}d_i\le|A|(n-1)+\sum_{j\in B}d_j-|A||B|-|\{j\in[2\nu]\mid j\in B\text{ and }2\nu+1-j\notin A\}|.

It remains to minimize the right-hand side over B⊆[n]∖AB\subseteq[n]\setminus A. Let

εj={1j∈[2ν] and 2ν+1−j∉A,0otherwise.\varepsilon_j= \begin{cases} 1 & j\in[2\nu]\text{ and }2\nu+1-j\notin A,\\ 0 & \text{otherwise}. \end{cases}

Including jj in BB contributes dj−∣A∣−εjd_j-|A|-\varepsilon_j to the right-hand side; excluding it contributes 0. Hence, minimizing the right hand side is equivalent to

min⁡B⊆[n]∖A(∣A∣(n−1)+∑j∈B(dj−∣A∣−εj))=∣A∣(n−1)+∑j∈[n]∖Amin⁡(0,dj−∣A∣−εj)=∣A∣(∣A∣−1)+∑j∈[n]∖Amin⁡(∣A∣,dj−εj)=∣A∣(∣A∣−1)+∑j∈[n]∖Amin⁡(∣A∣,dj)−∣{j∈[2ν]∣j∉A, 2ν+1−j∉A, dj≤∣A∣}∣.\begin{aligned} \min_{B\subseteq[n]\setminus A}\left(|A|(n-1)+\sum_{j\in B}(d_j-|A|-\varepsilon_j)\right) &=|A|(n-1)+\sum_{j\in[n]\setminus A}\min(0,d_j-|A|-\varepsilon_j)\\ &=|A|(|A|-1)+\sum_{j\in[n]\setminus A}\min(|A|,d_j-\varepsilon_j)\\ &=|A|(|A|-1)+\sum_{j\in[n]\setminus A}\min(|A|,d_j)\\ &\quad-\left|\{j\in[2\nu]\mid j\notin A,\ 2\nu+1-j\notin A,\ d_j\le|A|\}\right|. \end{aligned}

This is the required inequality.

The first two terms on the right-hand side in Lemma 5.4 give the usual degree-sum bound in the Erdős–Gallai Theorem. The subtracted term accounts for the prescribed matching. Accordingly, define, for every A⊆[n]A\subseteq[n],

h(A)=∑i∈Adi−∣A∣(∣A∣−1)−∑j∈[n]∖Amin⁡(∣A∣,dj),h(A)=\sum_{i\in A}d_i-|A|(|A|-1)-\sum_{j\in[n]\setminus A}\min(|A|,d_j),
g(A)=∣{j∈[2ν]∣j∉A, 2ν+1−j∉A, dj≤∣A∣}∣,g(A)=|\{j\in[2\nu]\mid j\notin A,\ 2\nu+1-j\notin A,\ d_j\le|A|\}|,
f(A)=h(A)+g(A).f(A)=h(A)+g(A).

Since dd is graphic, the degree-sum bound gives h(A)≤0h(A)\le0 for every AA. By Lemma 5.4, the cut constraints are therefore equivalent to f(A)≤0f(A)\le0 for every A⊆[n]A\subseteq[n].

Lemma 5.5. Under the assumptions of Theorem 5.2, inequalities (2) imply f([k])≤0f([k])\le0, for every integer k∈[n]k\in[n].

Proof. We consider three cases.

Case 1: If g([k])=0g([k])=0, then f([k])=h([k])≤0f([k])=h([k])\le0, since dd is graphic.

Case 2: If k≥νk\ge\nu, each pair {j,2ν+1−j}\{j,2\nu+1-j\} with j∈[2ν]j\in[2\nu] intersects [k][k]. Thus, g([k])=0g([k])=0, and Case 1 applies.

Case 3: Suppose k<νk<\nu and g([k])>0g([k])>0. Some index j∈[k+1,2ν−k]j\in[k+1,2\nu-k] then satisfies dj≤kd_j\le k. Since dd is non-increasing, the last kk degrees d2ν−k+1,…,d2νd_{2\nu-k+1},\ldots,d_{2\nu} are all at most kk, as well. Consequently, g([k])=∣{j∈[2ν]∖[k]∣dj≤k}∣−kg([k])=|\{j\in[2\nu]\setminus[k]\mid d_j\le k\}|-k. Using min⁡(dj−1,k)=min⁡(dj,k)−1\min(d_j-1,k)=\min(d_j,k)-1 when dj≤kd_j\le k, and min⁡(dj−1,k)=min⁡(dj,k)\min(d_j-1,k)=\min(d_j,k) otherwise, inequality (2) becomes

∑i=1kdi−k(k−1)−∑i=k+1nmin⁡(di,k)+∣{j∈[2ν]∖[k]∣dj≤k}∣−k≤0.\sum_{i=1}^{k}d_i-k(k-1)-\sum_{i=k+1}^{n}\min(d_i,k)+|\{j\in[2\nu]\setminus[k]\mid d_j\le k\}|-k\le0.

This is exactly h([k])+g([k])≤0h([k])+g([k])\le0.

We can now prove the characterization, namely Theorem 5.2. Proof of Theorem 5.2. Suppose first that dd has a realization with a matching of size ν\nu. By the Inverted Prefix Lemma (Lemma 2.3), there is a realization containing the inverted matching on the first 2ν2\nu vertices. Deleting these matching edges gives a realization of d′d'. By the Erdős–Gallai Theorem,

∑i=1kdi′≤k(k−1)+∑i=k+1nmin⁡(di′,k),1≤k<ν.(5)\sum_{i=1}^{k} d'_i \le k(k-1)+\sum_{i=k+1}^{n}\min(d'_i,k), \qquad1\le k<\nu. \tag*{(5)}

Substituting di′=di−1d'_i=d_i-1 for i≤ki\le k gives (2).

Conversely, suppose that (2) holds. By the flow equivalence and Lemmas 5.3 and 5.4, it suffices to prove that f(A)≤0f(A)\le0 for every A⊆[n]A\subseteq[n]. Suppose, towards a contradiction, that some set AA satisfies f(A)>0f(A)>0. Choose such a set A∗A_\ast of minimum cardinality, and let k=∣A∗∣k=|A_\ast|. Since all degrees are positive, f(∅)=0f(\varnothing)=0, so k≥1k\ge1.

First, we show that di≥kd_i\ge k for every i∈A∗i\in A_\ast. Otherwise, choose j∈A∗j\in A_\ast with dj<kd_j<k. Then

h(A∗∖{j})−h(A∗)=−dj+2(k−1)−min⁡(dj,k−1)+∣{i∉A∗∣di≥k}∣≥∣{i∉A∗∣di≥k}∣.\begin{aligned} h(A_\ast\setminus\{j\})-h(A_\ast) &=-d_j+2(k-1)-\min(d_j,k-1)+|\{i\notin A_\ast\mid d_i\ge k\}|\\ &\ge|\{i\notin A_\ast\mid d_i\ge k\}|. \end{aligned}

Lowering the cardinality threshold from kk to k−1k-1 can remove from the set counted by gg only indices of degree kk outside A∗A_\ast. Removing jj from A∗A_\ast cannot cause any further loss. Hence, g(A∗∖{j})−g(A∗)≥−∣{i∉A∗∣di=k}∣≥−∣{i∉A∗∣di≥k}∣g(A_\ast\setminus\{j\})-g(A_\ast)\ge-|\{i\notin A_\ast\mid d_i=k\}|\ge-|\{i\notin A_\ast\mid d_i\ge k\}|. It follows that f(A∗∖{j})≥f(A∗)>0f(A_\ast\setminus\{j\})\ge f(A_\ast)>0, contradicting the minimality of A∗A_\ast.

Next, suppose that j∈A∗j\in A_\ast and i∉A∗i\notin A_\ast satisfy di>djd_i>d_j, and let A∗′=(A∗∖{j})∪{i}A'_\ast=(A_\ast\setminus\{j\})\cup\{i\}. Since dj≥kd_j\ge k, we have h(A∗′)−h(A∗)=di−dj≥1h(A'_\ast)-h(A_\ast)=d_i-d_j\ge1. Also, di>kd_i>k, so ii is not counted by g(A∗)g(A_\ast). Replacing jj by ii can remove at most the index 2ν+1−i2\nu+1-i from the set counted by gg. Thus g(A∗′)−g(A∗)≥−1g(A'_\ast)-g(A_\ast)\ge-1, and f(A∗′)≥f(A∗)>0f(A'_\ast)\ge f(A_\ast)>0. Repeating this replacement, we may assume that the degrees indexed by A∗A_\ast are d1,…,dkd_1,\ldots,d_k, counted with multiplicities. In particular, {i∈[n]∣di>dk}⊆A∗\{i\in[n]\mid d_i>d_k\}\subseteq A_\ast. Indices of degree dkd_k may still be chosen arbitrarily, so A∗=[k]A_\ast=[k] need not hold.

We have dk≥kd_k\ge k and next show that dk>kd_k>k. Suppose that dk=kd_k=k. Every index outside A∗A_\ast then has degree at most kk. The indices counted by g(A∗)g(A_\ast) occur in pairs {j,2ν+1−j}\{j,2\nu+1-j\}, so g(A∗)g(A_\ast) is even. Moreover,

h(A∗)=∑i∈A∗di−∑i∉A∗di−k(k−1)=∑i=1ndi−2∑i∉A∗di−k(k−1).h(A_\ast)=\sum_{i\in A_\ast}d_i-\sum_{i\notin A_\ast}d_i-k(k-1)=\sum_{i=1}^{n}d_i-2\sum_{i\notin A_\ast}d_i-k(k-1).

Since dd is graphic, its degree sum is even. Thus h(A∗)h(A_\ast) is even, and f(A∗)>0f(A_\ast)>0 implies f(A∗)≥2f(A_\ast)\ge2. Choose j∈A∗j\in A_\ast with dj=kd_j=k. As in the first step,

h(A∗∖{j})−h(A∗)=−dj+2(k−1)−min⁡(dj,k−1)+∣{i∉A∗∣di≥k}∣=−1+∣{i∉A∗∣di≥k}∣.\begin{aligned} h(A_\ast\setminus\{j\})-h(A_\ast) &=-d_j+2(k-1)-\min(d_j,k-1)+|\{i\notin A_\ast\mid d_i\ge k\}|\\ &=-1+|\{i\notin A_\ast\mid d_i\ge k\}|. \end{aligned}

Also, g(A∗∖{j})−g(A∗)≥−∣{i∉A∗∣di≥k}∣g(A_\ast\setminus\{j\})-g(A_\ast)\ge-|\{i\notin A_\ast\mid d_i\ge k\}|. Therefore, f(A∗∖{j})≥f(A∗)−1>0f(A_\ast\setminus\{j\})\ge f(A_\ast)-1>0, again contradicting minimality.

Let [q]={i∈[n]∣di>dk}[q]=\{i\in[n]\mid d_i>d_k\} and [q+1,p]={i∈[n]∣di=dk}[q+1,p]=\{i\in[n]\mid d_i=d_k\}, and put l=∣A∗∩[q+1,p]∣=k−ql=|A_\ast\cap[q+1,p]|=k-q. We have [q]⊆A∗⊆[p][q]\subseteq A_\ast\subseteq[p]. The value of h(A∗)h(A_\ast) is unchanged by replacing indices within the block [q+1,p][q+1,p]. Since every degree indexed by A∗A_\ast exceeds kk,

g(A∗)=∣{j∈[2ν]∣dj≤k}∣−∣{j∈A∗∩[2ν]∣d2ν+1−j≤k}∣.g(A_\ast)=|\{j\in[2\nu]\mid d_j\le k\}|-|\{j\in A_\ast\cap[2\nu]\mid d_{2\nu+1-j}\le k\}|.

The indices j∈[2ν]j \in[2\nu] satisfying d2ν+1−j≤kd_{2\nu+1-j} \le k form a prefix of [2ν][2\nu]. Hence, replacing A∗∩[q+1,p]A_* \cap[q+1,p] by [p−l+1,p][p-l+1,p] can only decrease the second cardinality. This leaves h(A∗)h(A_*) unchanged and cannot decrease g(A∗)g(A_*) or f(A∗)f(A_*). We may therefore assume that A∗=[q]∪[p−l+1,p]A_*=[q]\cup[p-l+1,p].

For 0≤r≤p−q0 \le r \le p-q, define Ar=[q]∪[p−r+1,p]A_r=[q]\cup[p-r+1,p], so A∗=AlA_*=A_l. Let t=min⁡(dk−q,p−q)t=\min(d_k-q,p-q). Since dk>k=q+ld_k>k=q+l, we have t≥lt\ge l. We show that f(At)≥f(Al)>0f(A_t)\ge f(A_l)>0 by estimating the successive differences. For 1≤r≤t1\le r\le t, the new index p−r+1p-r+1 has degree dk>q+r−1d_k>q+r-1 and is not counted by g(Ar−1)g(A_{r-1}). Adding it can remove at most its partner 2ν+1−(p−r+1)2\nu+1-(p-r+1) from the set counted by gg. Increasing the threshold from q+r−1q+r-1 to q+rq+r can add only indices of degree q+rq+r. Consequently,

−1≤g(Ar)−g(Ar−1)≤∣{j∈[n]∣dj=q+r}∣.-1 \le g(A_r)-g(A_{r-1}) \le\lvert\{j\in[n]\mid d_j=q+r\}\rvert.

For the same range of rr, put m=q+rm=q+r. Every index in ArA_r has degree at least dk≥md_k\ge m, and therefore

h(Ar)−h(Ar−1)=dk−2(m−1)+min⁡(dk,m−1)−∣{j∉Ar∣dj≥m}∣=dk−(m−1)−∣{j∉Ar∣dj≥m}∣=dk+1−∣{j∈[n]∣dj≥m}∣.\begin{aligned} h(A_r)-h(A_{r-1})&=d_k-2(m-1)+\min(d_k,m-1)-\lvert\{j\notin A_r\mid d_j\ge m\}\rvert\\ &=d_k-(m-1)-\lvert\{j\notin A_r\mid d_j\ge m\}\rvert\\ &=d_k+1-\lvert\{j\in[n]\mid d_j\ge m\}\rvert. \end{aligned}

Applying the upper bound on g(Al)−g(Al−1)g(A_l)-g(A_{l-1}) gives f(Al)−f(Al−1)≤dk+1−∣{j∈[n]∣dj≥k+1}∣f(A_l)-f(A_{l-1})\le d_k+1-\lvert\{j\in[n]\mid d_j\ge k+1\}\rvert. Hence, for l+1≤r≤tl+1\le r\le t,

f(Ar)−f(Ar−1)≥dk−∣{j∈[n]∣dj≥q+r}∣≥dk−∣{j∈[n]∣dj≥k+1}∣≥f(Al)−f(Al−1)−1≥0.\begin{aligned} f(A_r)-f(A_{r-1})&\ge d_k-\lvert\{j\in[n]\mid d_j\ge q+r\}\rvert\\ &\ge d_k-\lvert\{j\in[n]\mid d_j\ge k+1\}\rvert\\ &\ge f(A_l)-f(A_{l-1})-1\\ &\ge0. \end{aligned}

Here l=k−q≥1l=k-q\ge1, and minimality gives f(Al−1)≤0<f(Al)f(A_{l-1})\le0<f(A_l). Since these values are integers, f(Al)−f(Al−1)≥1f(A_l)-f(A_{l-1})\ge1. Summing the differences yields f(At)≥f(Al)>0f(A_t)\ge f(A_l)>0.

Finally, consider two cases.

Case 1: If dk≥pd_k\ge p, then t=p−qt=p-q and At=[p]A_t=[p]. By Lemma 5.5, f(At)=f([p])≤0f(A_t)=f([p])\le0, a contradiction.

Case 2: If dk<pd_k<p, the preceding bound at r=lr=l gives

f(Al)−f(Al−1)≤dk+1−∣{j∈[n]∣dj≥k+1}∣≤dk+1−p≤0.f(A_l)-f(A_{l-1})\le d_k+1-\lvert\{j\in[n]\mid d_j\ge k+1\}\rvert\le d_k+1-p\le0.

The second inequality holds because all pp indices in [p][p] have degree at least dk>kd_k>k. This again contradicts f(Al)−f(Al−1)≥1f(A_l)-f(A_{l-1})\ge1.

Thus f(A)≤0f(A)\le0 for every A⊆[n]A\subseteq[n], completing the proof.

AI Disclosure

Chat-GPT-6 Astra was used to generate an initial version of the proof of Theorem 5.2, which was then simplified and rewritten by us. The tool was also used to help with the drawing of Figure 2, for spell checking and to enhance readability throughout the paper. We verified the correctness and originality of all content including references.

References

  1. [1]R. P. Anstee. An algorithmic proof of Tutte’s f-factor theorem. J. Alg., 6(1):112–131, 1985.DOI
  2. [2]R. P. Anstee. Simplified existence theorems for (g,f)-factors. Discr. Appl. Math., 27(1-2):29–38, 1990.DOI
  3. [3]A. Bar-Noy, I. Kalinichev, D. Peleg, and D. Rawitz. Degree realization with minimum dominating set. In 27th IPCO, volume 16588 of LNCS, pages 64–80, 2026.
  4. [4]M. D. Barrus. On realization graphs of degree sequences. Discrete Mathematics, 339(8):2146–2152, 2016.DOI
  5. [5]F. Bock and D. Rautenbach. On matching numbers of tree and bipartite degree sequences. Discr. Math., 342(6):1687–1695, 2019.DOI
  6. [6]V. Chungphaisan. Construction of hamiltonian graphs and bigraphs with prescribed degrees. J. Comb. Theory B, 24(2):154–163, 1978.DOI
  7. [7]P. Erdős and T. Gallai. Graphs with prescribed degrees of vertices [Hungarian]. Matematikai Lapok, 11:264–274, 1960.
  8. [8]P. L. Erdős, Z. Kiraly, and I. Miklos. On the swap-distances of different realizations of a graphical degree sequence. Combinatorics, Probability and Computing, 22:366–383, 2013.DOI
  9. [9]P. L. Erdős, S. R. Kharel, T. R. Mezei, and Z. Toroczkai. New results on graph matching from degree-preserving growth. Mathematics, 12(22), 2024.DOI
  10. [10]D. Fulkerson. Zero-one matrices with zero trace. Pacific J. Math., 10:831–836, 1960.DOI
  11. [11]D. R. Fulkerson, A. J. Hoffman, and M. H. McAndrew. Some properties of graphs with multiple edges. Canad. J. Math., 17:166–177, 1965.
  12. [12]M. Gentner, M. A. Henning, and D. Rautenbach. Largest domination number and smallest independence number of forests with given degree sequence. Discr. Appl. Math., 206:181–187, 2016.
  13. [13]M. Gentner, M. A. Henning, and D. Rautenbach. Smallest domination number and largest independence number of graphs and forests with given degree sequence. J. Graph Theory, 88(1):131–145, 2018.
  14. [14]R. J. Gould, M. S. Jacobson, and J. Lehel. Potentially G-graphical degree sequences. In Combinatorics, Graph Theory, and Algorithms, volume 1, pages 451–460, 1999.
  15. [15]S. L. Hakimi. On realizability of a set of integers as degrees of the vertices of a linear graph – I. SIAM J. Appl. Math., 10(3):496–506, 1962.DOI
  16. [16]V. Havel. A remark on the existence of finite graphs. Casopis Pest. Mat., 80:477–480, 1955.DOI
  17. [17]A. Kézdy and J. Lehel. Degree sequences of graphs with prescribed clique size. In Graph Theory, Combinatorics, Algorithms, and Applications, pages 535–544, 1999.
  18. [18]D. J. Kleitman and D. L. Wang. Algorithms for constructing graphs and digraphs with given valences and factors. Discr. Math., 6:79–88, 1973.DOI
  19. [19]S. Kundu. The k-factor conjecture is true. Discr. Math., 6(4):367–376, 1973.DOI
  20. [20]S. Kundu. A factorization theorem for a certain class of graphs. Discr. Math., 8(1):41–47, 1974.DOI
  21. [21]S. Kundu. Generalizations of the k-factor theorem. Discr. Math., 9(2):173–179, 1974.DOI
  22. [22]J. B. Orlin. Max flows in O(nm) time, or better. In 45th STOC, pages 765–774, 2013.DOI
  23. [23]A. Ramachandra Rao and S. Rao. On factorable degree sequences. Journal of Combinatorial Theory, Series B, 13(3):185–191, 1972.DOI
  24. [24]A. R. Rao. The clique number of a graph with a given degree sequence. In ISI Lect. Notes, volume 4, pages 251–267, 1979.
  25. [25]J.-H. Yin. A rao-type characterization for a sequence to have a realization containing a split graph. Discr. Math., 311(21):2485–2489, 2011.
  26. [26]J.-H. Yin. A short constructive proof of A. R. Rao’s characterization of potentially K_{r+1}-graphic sequences. Discr. Appl. Math., 160(3):352–354, 2012.DOI

Paper details

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

views · 10

downloads · 0

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

  • Computer Science

GPT-6 Astra (bare)

View statement
Looking for related papers…
Contents