# «Abstract For a graph G, denote by fk (G) the smallest number of vertices that must be deleted from G so that the remaining induced subgraph has its ...»

Large induced subgraphs with equated maximum degree

∗ †

Y. Caro R. Yuster

Abstract

For a graph G, denote by fk (G) the smallest number of vertices that must be deleted from G

so that the remaining induced subgraph has its maximum degree shared by at least k vertices.

√

It is not diﬃcult to prove that there are graphs for which already f2 (G) ≥ n(1 − o(1)), where

√

n is the number of vertices of G. It is conjectured that fk (G) = Θ( n) for every ﬁxed k. We prove this for k = 2, 3. While the proof for the case k = 2 is easy, already the proof for the case k = 3 is considerably more diﬃcult. The case k = 4 remains open.

A related parameter, sk (G), denotes the maximum integer m so that there are k vertexdisjoint subgraphs of G, each with m vertices, and with the same maximum degree. We prove that for every ﬁxed k, sk (G) ≥ n/k − o(n). The proof relies on probabilistic arguments.

1 Introduction All graphs considered in this paper are ﬁnite, simple, and undirected. Graph theory notation follows [2]. A vertex with maximum degree in a graph can be viewed, in many circumstances, as the “most inﬂuential” vertex in the graph. It may therefore be desired to distribute the inﬂuence among a few vertices of the graph. More formally, let m(G) denote the number of vertices of the graph G that attain the maximum degree. Clearly, m(G) = |V (G)| if and only if G is a regular graph, and, in the other obvious extreme, there are graphs in which m(G) = 1. Can we always guarantee that, after deleting just a few vertices of a given graph G, the remaining induced subgraph G has m(G ) ≥ k ?

This is the focus of the ﬁrst main result in this paper. We note that research concerning repetitions in the degree sequence of graphs (in this case, repetition of the maximum degree) has been treated by several researchers; see, e.g., [3, 4, 5, 7].

For a given positive integer k, let fk (G) denote the minimum number of vertices that we need to delete from G so that the remaining induced subgraph G has m(G ) ≥ k. Denote by fk (n) the maximum of fk (G) where G ranges over all graphs with n vertices. Trivially, f1 (n) = 0, and clearly f2 (n) is well deﬁned for all n ≥ 2. For completeness, we will set fk (n) = n whenever there is a graph G with n vertices for which no induced subgraph has m(G ) ≥ k. Thus, for example, f3 (4) = 4 as can be seen by taking the path with four vertices. It is easy to verify that f3 (n) ≤ n−3 ∗ Department of Mathematics and Physics, University of Haifa, Tivon 36006, Israel. email: yacaro@kvgeva.org.il † Department of Mathematics, University Haifa, Haifa 31905, Israel. email: raphy@math.haifa.ac.il

The case k = 4 of Conjecture 1.1 remains open. We are, however, able to verify Conjecture 1.1 for a large family of graphs. Recall that a graph is K2,t -free if no two vertices have t common neighbors.

Proposition 1.3 For ﬁxed integers k ≥ 2 and t ≥ 2, if G is a K2,t -free graph with n vertices then √ fk (G) = O( n).

The proofs of Theorem 1.2 and Proposition 1.3 appear in Section 2.

A related problem, along a line recently suggested in [6], asks for the deletion of as few as possible vertices so that the remaining vertices can be split into k equal parts, each inducing a subgraph with the same maximum degree. Formally, denote by sk (G) the maximum integer m so that there are k vertex-disjoint subgraphs of G, each with m vertices, and with the same maximum degree. Trivially, sk (G) ≥ n/k. However, it is easy to see that already s2 (G) may be smaller than n/2. Indeed, consider the star K1,n−1 when n is even. Clearly, s2 (K1,n−1 ) = n/2 − 1.

Nevertheless, we prove that sk (G) is very close to n/k for every ﬁxed k.

** Theorem 1.4 For any ﬁxed k, and for any graph G with n vertices, sk (G) ≥ n/k − o(n).**

The proof of Theorem 1.4 that appears in Section 3 also shows that k can, actually, be more than a constant. In fact, for suﬃciently small, Theorem 1.4 also holds for k = n where o(n) is replaced with o(n1− ).

2 Large induced subgraph with several maximum degree vertices √ We begin this section by observing that f2 (n) n(1 − o(1)). We construct a graph G with n = p2 vertices having the property that any induced subgraph with more than n − p + 2 vertices has a unique maximal vertex. This shows that f2 (G) ≥ p − 2. The vertex set of G will be denoted by V = {v1,..., vn }. The edge set of G is constructed as follows. For i = 0,..., p − 3, vertex vn−i will have degree n − (i + 1)p by arbitrarily choosing this amount of neighbors from {v1,..., vn−p+2 }.

Notice that the remaining n − p + 2 vertices have degree at most p − 2. Now, any subgraph that

Case 2: (x1, x2 ) ∈ E and there is no good vertex. In this case we delete x1 from G. Notice / that x1 is connected to all the vertices of Z and that x2 is not connected to any of the vertices of Z. After the deletion, the largest vertex is x2 and its degree is d2. The second largest vertex is x3 and its degree is d3 − 1. The third largest vertex is x4 and its degree is d4 − 1. Since the (now) ﬁrst largest vertex (x2 ) is not connected to the (now) second largest vertex (x3 ) and since x2 is also not connected to x4, we reduce to Case 1 and notice that x1 := x2, x2 := x3, x3 := x4, d1 := d2, d2 := d3 − 1 and d3 := d4 − 1. We notice also that when applying Case 1, the new x3 (which is the old x4 ) is a good vertex. Thus, in Case 1, the value of is at least d3 − d1 + d2 (in terms of the new di ’s) and hence, by (1), at most 3(d1 − d3 ) (in terms of the new di ’s) vertices are deleted to settle Case 1. In terms of the current di ’s we have that Case 2 can be settled directly by deleting at most 1 + 3(d2 − d4 + 1) = 4 + 3(d2 − d4 ) (2) vertices.

Case 3: (x1, x2, x3 ) form a triangle. We ﬁrst delete d1 −d2 neighbors of x1 that are not neighbors of x2. After the deletion, both x1 and x2 have maximum degree d2. The degree of x3 is and we have ≥ d3 − d1 + d2. We now perform the following operation for at most d2 − times, as long as there are no three vertices with the same maximum degree. If there is a neighbor common to x1 and x2 that is not a neighbor of x3 we delete it. Otherwise, we delete a neighbor of x1 that is not a neighbor of x3 and a neighbor of x2 that is not a neighbor of x3. Notice that in either case, the maximum degree is reduced by 1 and is still shared by x1 and x2, while x3 remained with degree. After performing this operation at most d2 − times we must have three vertices sharing the maximum degree. The overall number of vertices deleted in Case 3 is at most d1 − d2 + 2(d2 − ) ≤ d1 − d2 + 2(d1 − d3 ) ≤ 3(d1 − d3 ). (3) Case 4: (x1, x2 ) ∈ E, (x1, x3 ) ∈ E, (x2, x3 ) ∈ E. We delete x2 from G. After the deletion, x1 / / is still the largest vertex with degree d1 − 1, and x3 becomes the second largest vertex with degree d3. Since x1 is not connected to x3 we can now reduce to either Case 1 or Case 2. We notice that x1 := x1, x2 := x3, d1 := d1 − 1, d2 := d3, d3 :≥ d4 − 1 and d4 :≥ d5 − 1. Notice that if we reduce to Case 1 then, by (1), we can settle Case 4 directly by deleting at most 1 + 3(d1 − d5 ) vertices (in terms of the current di ’s) and if we reduce to Case 2 then, by (2), we can settle Case 4 directly by deleting at most 8 + 3(d3 − d5 ) vertices (in terms of the current di ’s). In any case, the number of vertices we need to delete in order to settle Case 4 directly is at most 8 + 3(d1 − d5 ). (4) Case 5: (x1, x2 ) ∈ E, d3 d4, and x3 is connected to precisely one of x1 or x2. If (x1, x3 ) ∈ E we delete x1. We reduce to either Case 1 or Case 2 with x1 := x2, x2 := x3, d1 := d2 − 1, d2 := d3 − 1, d3 :≥ d4 − 1 and d4 :≥ d5 − 1. Similarly, if (x2, x3 ) ∈ E we delete x2. Again we reduce to either Case 1 or Case 2 with x1 := x1, x2 := x3, d1 := d1 − 1, d2 := d3 − 1, d3 :≥ d4 − 1 and d4 :≥ d5 − 1.

Again, by (1) and (2) we see that in terms of the current di ’s, the number of vertices that we need to delete in order to resolve Case 5 directly is at most

Case 8: (x1, x2 ) ∈ E, d3 = d4 d5, (x3, x4 ) ∈ E and each of x3, x4 is adjacent to precisely one of x1 or x2. There are several sub-cases to consider.

If both x3, x4 are adjacent to x1, we delete x1 and reduce to Case 1 or Case 2 with x1 := x2, x2 := x3, x3 := x4, d1 := d2 − 1, d2 := d3 − 1, d3 := d3 − 1 and d4 :≥ d5 − 1. In terms of the current di ’s, the number of vertices that we need to delete in order to resolve this subcase of Case 8 directly is at most 5 + 3(d2 − d5 ).

Similarly, if both x3, x4 are adjacent to x2, we delete x2 and reduce to Case 1 or Case 2 with x1 := x1, x2 := x3, x3 := x4, d1 := d1 − 1, d2 := d3 − 1, d3 := d3 − 1 and d4 :≥ d5 − 1. In terms of the current di ’s, the number of vertices that we need to delete in order to resolve this subcase of Case 8 directly is at most 5 + 3(d1 − d5 ).

Finally, we can assume that (x1, x3 ) ∈ E and (x2, x4 ) ∈ E and hence (x1, x2, x3, x4 ) induce a 4-cycle. We delete a set of d2 − d3 neighbors of x2 that are not neighbors of x4. After this deletion, the degree of x2 and x4 is d3, while the degree of x1 is at least d1 − d2 + d3 and the degree of x3 is at least 2d3 − d2. Thus, we can reduce to Case 1 or Case 2 with x1 := x1, x2 := x4, x3 := x2, x4 := x3 and d1 :≥ d1 − d2 + d3, d2 := d3, d3 := d3, d4 :≥ 2d3 − d2. If we reduce to Case 1, then by (1), we can settle this subcase of Case 8 directly by deleting at most d2 − d3 + 3(d1 − 2d3 + d2 ) ≤ 7(d1 − d3 ) (all in terms of the current di ’s). If we reduce to Case 2, then by (2), we can settle this subcase of Case 8 directly by deleting at most d2 − d3 + 4 + 3(d3 − 2d3 + d2 ) = 4 + 4(d2 − d3 ) (all in terms of the current di ’s).

Considering all the above subcases of Case 8, we see that in terms of the current di ’s, the number of vertices that we need to delete in order to resolve Case 8 directly is at most

3 Disjoint induced subgraphs with equal order and maximum degree Proof of Theorem 1.4: For the rest of the proof, we assume that k ≥ 2 is ﬁxed and that G is an n-vertex graph. Whenever necessary we shall assume that n is suﬃciently large, as this does not aﬀect the asymptotic result.

Consider ﬁrst the case where ∆(G) (the maximum degree of G) is at most n1/4. We perform the following process. If m(G) k∆(G)2, then we can clearly select k vertices of G with maximum degree ∆(G) with the property that no two of them are neighbors or have a common neighbor.

Thus if v1,..., vk are such vertices, we can deﬁne k pairwise vertex-disjoint subgraphs of G, each with n/k vertices, as follows. Gi will contain vi and all of its neighbors, for i = 1,..., k, and the other vertices of G are assigned arbitrarily to the Gi. Notice that each Gi has maximum degree ∆(G), as required, and hence sk (G) = n/k in this case. Otherwise, we can assume that m(G) k∆(G)2. So we modify G by deleting from it all the m(G) vertices with maximum degree.

We have deleted less than k∆(G)2 ≤ kn1/2 vertices and the new graph has maximum degree at most n1/4 − 1. We now repeat the same process as before. Notice that the process consists of at most n1/4 steps (as each step decreases the maximum degree) and that in each step we delete less than kn1/2 vertices. Thus, once we halt we have only deleted at most kn3/4 vertices and hence sk (G) ≥ (n − kn3/4 )/k = n/k − o(n), and we are done.