Some extremal problems of graphs with local constraints Original Research Article

Let P be a family of graphs. A graph G is said to satisfy a property P locally if G[N(v)]∈P for every v∈V(G). The class of graphs that satisfies the property P locally will be denoted by L(P) and we shall call such a class a local property. Let P be a hereditary property. A graph is said to be maximal with respect to a hereditary property P (shortly P-maximal) if it belongs to P and none of its proper supergraphs of the same order has the property P. A graph is P-extremal if it has the maximum number of edges among all P-maximal graphs of given order. This number is denoted by ex(n,P). If the number of edges of a P-maximal graph of order n is minimum, then the graph is called P-saturated and its number of edges is denoted by sat(n,P). In this paper, we shall describe the numbers ex(n,L(Ok)) and ex(n,L(Sk)) for k⩾1. Also, we give sat(n,L(Ok)) and sat(n,L(Sk)) for k=1,2