Studying Properties of Graphs through their k-vertex Subsets: I IIκ-complete Graphs and IIκ-completion numbers

There are several concepts in graph theory which involve vertex subsets of cardinality two: an edge is a connected vertex subset of cardinality two, a clique is a vertex subset such that any two of its vertices induce a connected subgraph, and an independent set is a vertex subset such that any two of its vertices induce a disconnected subgraph. These concepts motivated us to study various graph theoretic properties denned through k-vertex-subsets, where k is any integer, rather than 2. s paper all our graphs are simple and possibly infinite. For convenience, we say that a vertex subset S of a graph G(V, E) has property II, if the induced subgraph (S) has property II. Let Pk(V) and Xk(V) respectively denote the set of all k-vertex-subsets and the set of all connected k-vertex-subsets in G.