Skip to main content
1 of 3
Ozzy
  • 393
  • 2
  • 12

Maximal subgraphs with dense connections

Let G=(V,E) be a given network. Denote by $S_k \subset V$ be the maximal subset of nodes such that in the induced subgraph $G_k=(S_k, E_k)$ (where $E_k=E\cap S_k \times S_k$), all agents have at least $k$ connections, i.e., $i\in S_k \Rightarrow \sum_{j\in S_k} g_{ij}\geq k$, where $G$ denotes the unweighted adjacency matrix.

My question is whether for a given $k$ the set $S_k$ corresponds to a known quantity in the graph theory literature. I am interested in understanding how the cardinality of set $S_k$ changes as a function of $k$ for different families of graphs (or certain random graph models).

Ozzy
  • 393
  • 2
  • 12