# Name for set of vertices that are pairwise within distance two

A 2-stable set (or a distance-two independent set) of a graph $$G$$ is a set of vertices which are pairwise at a distance greater than 2 in $$G$$.

Is there a name for a set of vertices which are pairwise at a distance at most 2?

Such a set for a graph $$G$$ is basically a clique in the square graph $$G^2$$ of G. Are there any papers that study (or at least mention) this parameter?

Update (2022-03-09):
A set of vertices $$S$$ in a graph $$G$$ such that $$d_G(u,v)\leq 2$$ for all $$u,v\in S$$ is called a '2-clique' in $$G$$ (2nd definition here: [1]; usual meaning of $$k$$-clique is a clique of size $$k$$). Another related concept is that of a 2-club (also called 2-clan). A 2-club in $$G$$ is a set of vertices $$S$$ in $$G$$ such that $$d_{G[S]}(u,v)\leq 2$$ for all $$u,v\in S$$ [2]. I am interested in '2-cliques', not 2-clubs. A clique in $$G^2$$ is a '2-clique', not a 2-club. Thanks to JimN for directing me to the youtube channel Wrath of Math and thus to [1].

• Perhaps: The vertex set of a subgraph with diameter at most $2$. Mar 7 at 13:10
• Subgraph of diameter 2 is exactly what I am interested in. In this question, they call such maximal subgraphs as diameter-2 clques. Mar 8 at 1:38
• Sorry for the confusion. A subgraph of diameter two is not what I want (it is a 2-club). I am interested in clique in square graph. The difference is that a clique $S$ in $G^2$ can contain two vertices $u$ and $v$ such that $d_G(u,v)=2$, but $d_{G[S]}(u,v)>2$. Mar 9 at 3:06

## 1 Answer

There are a number of related notions which could be what you are asking depending on whether the shortest paths between a pair of nodes in a set $$S$$ are allowed to use nodes outside of the set $$S$$ or not.

I believe these notions date back to Mokken (1979) who called these variants '$$k$$-cliques', '$$k$$-clans' and '$$k$$-clubs' in a sociological context. See also this video that distinguishes them https://www.youtube.com/watch?v=hw3VJCTgnIA (but also mentions that maybe people since then have used some of these terms interchangeably). One should always be clear about which definition they are using.

• Thanks for your answer. I am interested in 2-clques (defined in this youtube video by Wrath of Math). Sorry for confusing 2-cliques with 2-clubs. Mar 9 at 2:44
• Could you please mention about 2-cliques also in your answer? (please see the update to the question). I would like to upvote this answer for directing me to the notion of 2-clique. Mar 9 at 2:58
• The name 2-clique is used in Mokken (Cliques, clubs and clans) as well. Mar 9 at 4:02
• @CyriacAntony I have edited the response to include the k-clique terminology. If k-clique is the only term you think you are after here and you want to credit an original source, I believe Mokken cites that back to Luce(1950) or Alba(1973)
– JimN
Mar 9 at 6:39