Minimum \((n,k,t)\) clique graphs (Q2799814)

Suppose that \(n\geq k\geq t\) are positive integers. An \((n,k,t)\) graph is a graph \(G\) of order \(n\) such that every induced subgraph of order \(k\) contains a clique of order \(t\). A minimum \((n,k,t)\) graph is an \((n,k,t)\) graph with the minimum number of edges among \((n,k,t)\) graphs. An interesting problem in this subject is describing the minimum \((n,k,t)\) graphs for all \((n,k,t)\). The authors examined a few easy cases of the minimum \((n,k,t)\) graph problem, \(n\geq k\geq t\). For \(t=1\), the unique minimum \((n,k,1)\) graph is the empty graph of order \(n\). For \(k=t\geq 2\), the graph \(G\) is \(K_n\). For \(n=k\), the unique minimum \((n,n,t)\) graph is \((n-t)K_1\cup K_t\). For \(t=2\), the unique minimum \((n,k,2)\) graph is the disjoint union of \(K_{p_i}\) (\(1\leq i\leq k-1\)), where \(p_1\leq\dots\leq p_{k-1}\leq p_1+1\), \(p_1+\dots+p_{k-1}=n\). More cases are also considered in the paper.