WorksMathematics
The size and structure of graphs with a unique -factor
Abstract
For integers with even, let be the maximum size of a graph of order with a unique -factor. In 1964, Hetyei and in 1984, Hendry [J. Combin. Theory Ser. B 37 (1984), 53–63] proved for even and , respectively. In 2000, Johann [J. Graph Theory 35 (2000), 227–243] showed that for and even and for , where is a positive integer. Later, Volkmann [Combinatorica 24 (2004), 531–540] proved for and even, and he determined . In this paper, we determine for all admissible pairs, proving the size conjecture posed by Volkmann. We also prove that every extremal graph with has a universal vertex whose neighbors in the unique factor are precisely its degree- 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 are and , respectively. For , let denote its degree. For , let be the induced subgraph; for disjoint , let count the edges between them. Write . A vertex adjacent to every other vertex is universal. We denote by the complete graph of order , by the complete bipartite graph with partite sets of sizes and , and by the complement of . For disjoint graphs and , their join is obtained from their disjoint union by adding all edges between and .
For a function , an -factor is a spanning subgraph satisfying for every . If for every vertex , then is called a -factor. For integers with even, define
Whenever is the unique -factor, we color its edges red and the remaining edges of blue, and write and . We use and for the red and blue neighborhoods of the vertex .
E-mail addresses: [email protected] (Z. Yang)
In 1964, Hetyei (see Corollary 1.6 in [9]) determined , and in 1984, Hendry [2] determined . In 2000, Johann [7] proved the general bound
with equality when is a multiple of , and determined the maximum graphs when . Later, Volkmann [10] determined for and for , and supplied constructions for all suitable positive integers and .
Let , , and , and define
Define
Volkmann [10] conjectured that for all suitable positive integers and .
Conjecture 1.1 (Volkmann, [10]). For positive integers and even, .
Our first result proves Conjecture 1.1.
Theorem 1.2. Let be integers such that is even. If with , then
Remark. The previously determined cases include , the range , and the residue classes . Outside these ranges, the unresolved cases of the conjecture are contained in , , and , subject to 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 -factor, , has minimum degree at most ; see also Akbari, Ghodrati, and Hosseinzadeh [1 Corollary 1.5]. For a graph with a unique -factor, Volkmann [10] gave the following conjecture.
Conjecture 1.3 (Volkmann, [10]). Let be a graph of order with a unique -factor such that . If is of maximum size, then contains exactly vertices of degree .
Our second result shows the following stronger statement.
Theorem 1.4. Let , and let be a graph of order and size with unique -factor . Then has size . Moreover, has a universal vertex such that .
Some technical lemmas
The following theorem will be used when every prescribed degree is positive.
Theorem 2.1 (Jackson and Whitty, [6]). Let be a -edge-connected graph with a unique -factor, where for every . Then some vertex satisfies .
We recall the following necessary factor inequality, which is a corollary of Lovász’s -factor theorem [8] with for every vertex . For a function , write .
Proposition 2.2. Let be a graph with a -factor, where . If partition , then
Fix a finite vertex set and . We call a graph on -extremal if it has a unique -factor and has maximum size among graphs on with a unique -factor. For , write . If is its unique factor, a vertex is free if , and tight if and .
Lemma 2.3. Let be -extremal with unique -factor . Then the following two statements hold:
(i) if is free, then is universal, and is extremal for ;
(ii) if is tight, then every edge incident to belongs to , and is extremal for the function for every .
Proof. We prove the two statements separately.
(i) Let be a free vertex. Since , every -factor has degree at . It follows that no edge incident to can be used in any -factor of .
We now show that is universal. Suppose, for contradiction, that is not universal. Then there exists some vertex with . Let . Since edges incident to cannot belong to any -factor, the set of -factors of is exactly the same as the set of -factors of . In particular, still has a unique -factor . However, , which contradicts the assumption that is -extremal. Hence is universal.
We next prove that is extremal for . Suppose, for contradiction, that is not extremal. Note that has a unique -factor, namely , since every such factor extends to an -factor of by adjoining as an isolated vertex. Thus there exists a graph on vertex set such that and has a unique -factor. Construct a new graph on by adding the vertex to and joining to every vertex in . Since remains free, the -factors of are in bijection with the -factors of , so has a unique -factor. Since is universal in , we have
contradicting the extremality of . Therefore must be -extremal.
::: (ii) Let be a tight vertex. Then and . Note that every -factor of contains all edges incident to . Indeed, for any -factor , we have . As is a spanning subgraph of , this equality forces to contain all edges incident to . Also, for every , since implies . We now establish a bijection between the set of -factors of and the set of -factors of . Let be any -factor of . Since must contain all edges incident to , the subgraph satisfies
for all . Hence is an -factor of . Conversely, let be any -factor of . Construct a spanning subgraph on by setting , where is the set of edges incident to in . Then and
for all , so is an -factor of . These two constructions are inverse to each other. Since has a unique -factor, it follows immediately that has a unique -factor, namely .
It remains to show that is -extremal. Suppose, for contradiction, that there exists a graph on with and a unique -factor. Construct a new graph on by adding the vertex to , and joining exactly to its neighbors in . Since , every -factor of contains all edges incident to . Hence the same bijection argument shows that has a unique -factor, and
which contradicts the extremality of . Hence is -extremal. □
Theorem 2.4. Let be an -extremal graph of positive order with unique -factor . If for every , then has a tight vertex.
Proof. We use induction on . For , a graph of order one cannot admit an -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 has no tight vertex.
Claim 1. is connected.
Proof of Claim 1. Suppose to the contrary that is disconnected, and let be the vertex set of one connected component. Add an edge joining a vertex in to a vertex in , and denote the enlarged graph by . Since is the vertex set of a component of , the existing factor gives , which is even. For any -factor of , the total degree sum over satisfies
where is the number of edges in crossing the cut between and . Since is even, has the same parity as . In , the only edge crossing this cut is the newly added edge , so . Thus cannot be contained in any -factor of . It follows that the set of -factors of is identical to that of , so still has a unique -factor. However, , contradicting the assumption that is -extremal. Hence the claim holds. □
If has no bridge, then it is 2-edge-connected, and by Theorem 2.1, there exists a vertex with , contradicting our assumption. So we assume that has a bridge. Let be a bridge of , and let be the vertex sets of the components of , with and . Let , for , and for . Note that and , while for all and for all .
For any -factor of , by the same parity argument as before, we have
Since the left-hand side is fixed, is uniquely determined by parity. It therefore equals , the value taken by the unique factor . In other words, every -factor of contains the bridge if and only if does, which establishes a bijection between the -factors of and pairs consisting of an -factor of and an -factor of , combined with the fixed status of . Since has a unique -factor, both and have unique factors for their respective degree functions, namely and . 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 would still be the only edge between and . Its membership in an -factor would still be fixed by the parity identity (1). The same correspondence would therefore yield a larger graph on with a unique -factor, contradicting the extremality of .
We now consider two cases based on whether the bridge belongs to the unique factor.
Case 1: .
Since , we have , so for all . By the induction hypothesis, the -extremal graph contains at least one tight vertex.
By repeatedly applying Lemma 2.3(ii), we may delete tight vertices one by one from , 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 . 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 , we obtain a residual graph containing a free vertex .
We now construct a new graph from by removing the bridge , and adding all edges between and vertices in . We claim that still has a unique -factor. Since , the only removed edge lies outside , so remains an -factor of . Since , no added edge is incident to any . Moreover, after removing and the preceding vertices , the edges incident to are exactly those at the corresponding stage of the deletion process in . The vertex is therefore tight in , so all its incident edges are forced into any -factor. After deleting , the same holds for , and so on, up to . After removing all these tight vertices, the residual prescribed degree of is , so none of the new edges incident to can be contained in any factor. The residual factor on is unique by the repeated applications of Lemma 2.3(ii), and the factor on is unique because has a unique -factor. Hence the -factor of is unique.
We now count edges. Note that we removed one edge (namely ) and added edges. So we have
Since , the graph is an -factor of . As for every , it follows that . Thus . This contradicts the extremality of .
Case 2: .
We first assert that and . Suppose for contradiction that . Then , so for all . By induction, contains an -tight vertex . If , then , which implies that is tight in , contradicting our assumption. If , then . Consequently,
which implies that is tight in , again a contradiction. Hence , and by symmetry .
With and , we have and , which means that and are two free vertices in and , respectively. By Lemma 2.3(i), free vertices in extremal graphs are universal. Therefore, and are adjacent to every vertex in and , respectively.
Notice that and are both nonempty. Indeed, if , then has only the bridge as its incident edge, which implies that . Thus is a tight vertex, which contradicts our assumption. The same holds for .
We now construct a new graph as follows: (i) retain all edges of and , and retain the bridge ; (ii) join to all vertices in (retaining the original edges from to , and adding edges from to every vertex in ); (iii) remove all edges between and , so that is adjacent only to ; and (iv) choose arbitrary vertices and , and add the edge .
We first verify the edge count. In the original graph , there are edges between and . In , we remove these edges, add edges from to , and add the edge . All other edges are unchanged. Since was the only edge between and , the added edges were not contained in . Thus, we have
which means that has strictly more edges than .
Since and , none of the removed edges between and belongs to . Thus remains an -factor of . To contradict the extremality of , it remains to show that has a unique -factor. Since and , the edge must be included in every -factor. Since , including gives its prescribed degree. Thus no other edge incident to can belong to any -factor. After excluding all other edges incident to , the only edge still available to a factor across the cut between and is . The sum of the prescribed degrees on is , which is even. Any factor must use an even number of edges across this cut, so the single edge cannot be contained in the factor. Consequently, apart from , every edge of an -factor belongs to or . By Lemma 2.3(i) applied to the free vertices and of and , respectively, each of these graphs has a unique factor for the restriction of . Together with the forced edge , these two factors determine the unique -factor of , contradicting the extremality of .
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 such that, with , , and , each is -extremal, and is either free and universal in , or tight in .
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 be a bipartite graph with partite sets and such that for each . If and is the nondecreasing degree sequence on , then
where for .
Proof. If , then both sides are zero. So we may assume that . We form the bipartite graph with two partite sets and , and with if and only if . Note that .
Claim 2. For every , .
Proof of Claim 2. For every , the inclusion and the equality show that
Counting the edges of between and from each partite set, we obtain that
This proves the claim.
Let be an ordering of so that . For , let . Then . Indeed, since , the vertex has neighbors in , and each such neighbor satisfies . Moreover, we have , and
Write . For every integer , define . Thus . When , this is a set of vertices with the smallest values of ; when , it is empty.
We now apply the inequality in Claim 2 to a family of subsets of . Since , its intersection with consists of those with . Therefore . Note that every subset of of size has degree sum at least the sum of the smallest degrees. Hence
Substituting into the inequality in Claim 2 and combining with the above identities, we obtain that
For every integer , we have
Indeed, write with integers and . If , then , so ; this contributes terms equal to . If , then , which implies that . If , then , so and the summand vanishes. Summing these contributions, we obtain
For , both sides of (3.2) are zero. Thus we may sum (3.2) over all ; 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 ,
Using (2), this simplifies to
The sum of the left-hand side of (3.2) over is . For a fixed index , the term appears in the inner sum if and only if , or equivalently . Since runs over positive integers, the number of such indices is exactly . Interchanging the order of summation, we have
Combining (3.2), (5), and (6), we have
By the handshaking lemma for bipartite graphs, the total degree sum over equals the total degree sum over , i.e.,
Substituting the above equality into (7), we have
This completes the proof of Lemma 3.1.
Let and be two positive integers such that is even and . To establish a lower bound for , we introduce some families of graphs of order with a unique -factor.
Example 3.2 (see Example 3.1 in [10]). Let and be positive integers. We construct the graph that is of size and has a unique -factor by considering two cases. In both cases, the prescribed degrees on lie between and and sum to . To realize them, list the vertices of cyclically times, partition the list into consecutive segments of the prescribed lengths, and join each vertex of to its segment. Each segment has distinct entries, and every vertex of has degree .
Case 1. and . Let be the bipartite graph with the partite sets and such that and with
Next we connect the vertices of and by edges such that for all , for , for , for , and for . It is a simple matter to see that one can realize such a bipartite graph and
Now the graph of order originates from by connecting all pairs of vertices in by an edge. Every -factor contains all edges of , since every vertex of has degree . The vertices therefore have degree zero in the remaining factor on . Each must be adjacent in this factor to all other vertices of , which has order . This gives every its remaining degree , and forces the vertices to induce . Thus the remaining factor, and hence the -factor of , exists and is unique.
Case 2. with and even. Let be the bipartite graph with the partite sets and such that and with
Next we connect the vertices of and by edges such that for all , for , for , and for . Clearly, one can realize such a bipartite graph and
Now the graph of order originates from by connecting all pairs of vertices in by an edge. Again, every -factor contains all edges of , and the vertices
have degree zero in the remaining factor on . Each must be adjacent in this factor to all other vertices of , which has order . These edges give every its remaining degree . Thus the remaining factor exists and is unique in this case as well.
We next introduce another family of graphs .
Example 3.3 (see Example 5.1 in [10]). For with even, if is a -regular graph of order , then the graph is of size and has a unique -factor. Such a graph exists since and is even. Now let , , and be positive integers such that and with and even. Construct different families of graphs of order as follows: take disjoint copies of labelled .
Case 1. For define .
Case 2. For define (cf. Example 3.2).
Case 3. For define and .
For each and with in the first two cases and in the third case, add the edges connecting all vertices of the in to all the vertices of . It can easily be verified that has a unique -factor, and its size is .
For , the construction uses ordered blocks. A standard block has two sets of size , with independent, complete, and all edges between them. Its unique -factor is . Add all edges from to every later block.
When , use standard blocks. When , use standard blocks followed by the graph . When , use standard blocks followed by Hendry’s graph . In the range , use itself, with understood as a standard block.
The degree- vertices in the first standard block force its factor, giving every vertex of that block degree 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 , as in Example 3.3. Indeed, prepending a standard block to a graph of order adds
edges; the final blocks have the stated sizes. In particular,
Proof of Theorem 1.2. Let be a graph of order and size with unique -factor . Color the edges of red and all other edges of blue. Write , where and . Use the ordering from Corollary 2.5. Let . Call the deletion of free when and tight otherwise. At each step, a free vertex is universal in the remaining graph, while a tight vertex has remaining degree . Let be the free vertices in deletion order, with positions , and let be the set of the other vertices.
If and is free, then is blue; and if is tight, every remaining edge incident to is red. Consequently, with , we have
Note that the free vertices are independent in . 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 , , and . Note that , since every red neighbor of precedes , and hence every vertex of precedes . So by (9), we have
We now construct an auxiliary bipartite graph to apply Lemma 3.1. For , let be the number of red neighbors among the free vertices. Since each free vertex has red neighbors, we have . Define a bipartite graph with partite sets and by joining to when is a red neighbor of . Every vertex in the second partite set has degree . As in Lemma 3.1, set . Double-counting the pairs with shows , since, if is the first free red neighbor of , then belongs to exactly and ; if has no free red neighbor, both contributions are zero.
Let be the degree sequence of on , and let , , , and . Then is the non-increasing degree sequence of ,
and (since combining and gives ). By Lemma 3.1, we have
For , write . Then by the same counting argument as in Lemma 3.1, we have
Let be a set of vertices of largest degree in . Write . We decompose the degree sum over as
The degree sum over the complement is
which implies that . Since is simple, . Therefore
i.e., . Moreover, each vertex in has degree at most , so , and the total degree sum of is , so . Thus
To bound , we first use only the numerical constraints and , together with the fact that the weights are non-increasing. Under these numerical constraints, if , , and , replace and by and , respectively, where . This preserves the constraints and does not decrease the weighted sum. Repeating these exchanges, we obtain in each of the first positions and in all remaining positions. Hence . By (11), we have
Here the equality uses and . Combining (10) and (14), we have
Then the first difference is
which is strictly decreasing in .
Let , and let . If , with , then
Using and the expansion of (15), we obtain that
Suppose first that , and let . If , then ; and if , then the red neighbors of each free vertex belong to , giving . In this range (), and hence . So
It follows that , including .
Now assume that . If , then we let . By (16),
which, since the first differences are strictly decreasing, shows that and maximize . At , we have . So by (17), we obtain that .
If , then we let . Since , by (16), we have
Thus and again maximize . At , we have and , whence, by (17),
Therefore also holds.
It remains to consider . We discuss two cases according to .
Case 1: .
Since , by (16), we have . Thus is nondecreasing on the integer range . Let be the least integer at least of the same parity as . Let , where
The largest in this range is , and , where . Subtracting from (17), we have
When , is a positive odd integer, so the first expression is nonnegative. When , the second expression is positive. Hence .
Case 2: .
Write , where and ; if divides , take . Here since . In particular, , and (12) can be rewritten as . In (12), all the partial sums except the last have indices at least , and the last is . Apply to the first partial sums, and apply (13) to , to obtain that
Also,
Substituting (18) and (19) into (11) and then (10), and using , we obtain that
Since and , we have . On the other hand, since and , . For , we have and . Thus the only integer in this interval congruent to modulo is itself, so . Therefore , which is exactly .
Since the unique factor has edges,
The examples in this section give . Hence . 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 with the unique -factor , 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 be the vertices deleted before this step, listed in deletion order, and let . Let 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 incident to a vertex of , its earlier endpoint in the deletion ordering also belongs to . The edge is still present when that endpoint is deleted tightly, so it is red. As a result, every vertex in has degree exactly in the original graph .
Claim 3. .
Proof of Claim 3. We first show that . Note that the initial factor degree of is , and its residual prescribed degree becomes after deleting the vertex set . Thus , and . Therefore .
Next we prove that by contradiction. Suppose that . We construct an enlarged graph by adding all edges from to vertices in . These edges are not in . Indeed, otherwise, if a vertex were adjacent to , then would be red, contrary to .
We now verify that has a unique -factor. Since no edge is removed, remains a -factor of . The vertices in are unaffected by the newly added edges, so they still have degree in . Consequently, all their incident edges must be included in any -factor of . In particular, the red edges between and are forced into every factor, giving its prescribed degree . Consequently, none of the newly added edges incident to can belong to any -factor. Thus the set of -factors of is identical to that of , which implies that the factor of is unique.
On the other hand, one can see that , contradicting the assumption that is a maximum-size graph with a unique -factor. Therefore , completing the proof of the claim.
Since and both sets have size , we have .
We assert that is a universal vertex of . Repeated applications of Lemma 2.3(ii) show that is extremal for the residual degree function
Furthermore, is a free vertex in . By Lemma 2.3(i), every free vertex in an extremal graph is universal, so is adjacent to all other vertices in . Since is also adjacent to every vertex in (as ), it follows that is adjacent to every other vertex in . Hence the assertion holds.
By the assertion of the universal vertex of , , since . For any other vertex , is blue because is universal and . Together with the red edges incident to , this gives . Thus, by Claim 3, and .
The proof of Theorem 1.4 is complete.
References
- [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]G. R. T. Hendry, Maximum graphs with a unique k-factor, J. Combin. Theory Ser. B 37 (1984), 53–63.DOI
- [3]A. Hoffmann and L. Volkmann, On unique k-factors and unique [1, k]-factors in graphs, Discrete Math. 278 (2004), 127–138.
- [4]A. Hoffmann and L. Volkmann, Structural remarks on bipartite graphs with unique f-factors, Graphs Combin. 21 (2005), 421–425.
- [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]B. Jackson and R. W. Whitty, A note concerning graphs with unique f-factors, J. Graph Theory 13 (1989), 577–580.DOI
- [7]P. Johann, On the structure of graphs with a unique k-factor, J. Graph Theory 35 (2000), 227–243.DOI
- [8]L. Lovász, Subgraphs with prescribed valencies, J. Combinatorial Theory 8 (1970), 391–416.DOI
- [9]L. Lovász, On the structure of factorizable graphs I, Acta Math. Acad. Sci. Hungar. 23 (1972), 179–195.DOI
- [10]L. Volkmann, The maximum size of graphs with a unique k-factor, Combinatorica 24 (2004), 531–540.