2017/04/27 by Caro, Yair, Lauri, Josef, Zarb, Christina
#05C07 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1704.08472
Given a graph G, we would like to find (if it exists) the largest induced subgraph H in which there are at least k vertices realizing the maximum degree of H. This problem was first posed by Caro and Yuster. They proved, for example, that for every graph G on n vertices we can guarantee, for k = 2, such an induced subgraph H by deleting at most 2√(n) vertices, but the question if 2√(n) is best possible remains open. Among the results obtained in this paper we prove that: 1. For every graph G on n ≥ 4 vertices we can delete at most \lceil (- 3 + √( 8n- 15))/(2 ) \rceil vertices to get an induced subgraph H with at least two vertices realizing Δ(H), and this bound is sharp, solving the problems left open by Caro and Yuster. 2.For every graph G with maximum degree Δ≥ 1 we can delete at most \lceil ( -3 + √(8Δ+1))/(2 ) \rceil vertices to get an induced subgraph H with at least two vertices realizing Δ(H), and this bound is sharp. 3. Every graph G with Δ(G) ≤ 2 and least 2k - 1 vertices (respectively 2k - 2 vertices if k is even) contains an induced subgraph H in which at least k vertices realise Δ(H), and these bound are sharp.