MathDB
t-group and central point

Source: 2012 China TST Test 2 p1

March 19, 2012
algorithminductioncombinatorics proposedcombinatorics

Problem Statement

In a simple graph GG, we call tt pairwise adjacent vertices a tt-clique. If a vertex is connected with all other vertices in the graph, we call it a central vertex. Given are two integers n,kn,k such that 32≤12n<k<n\dfrac {3}{2} \leq \dfrac{1}{2} n < k < n. Let GG be a graph on nn vertices such that (1) GG does not contain a (k+1)(k+1)-clique; (2) if we add an arbitrary edge to GG, that creates a (k+1)(k+1)-clique. Find the least possible number of central vertices in GG.
Back to ProblemsView on AoPS