<p>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 <span class="math-container">$S$</span> are allowed to use nodes outside of the set <span class="math-container">$S$</span> or not.</p>
<p>I believe these notions date back to Mokken (1979) who called these variants '<span class="math-container">$k$</span>-cliques',  '<span class="math-container">$k$</span>-clans' and '<span class="math-container">$k$</span>-clubs' in a sociological context. See also this video that distinguishes them <a href="https://www.youtube.com/watch?v=hw3VJCTgnIA" rel="nofollow noreferrer">https://www.youtube.com/watch?v=hw3VJCTgnIA</a> (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.</p>
<ul>
<li>Mokken, Cliques, clubs and clans, Quality and Quantity volume 13, pages161–173 (1979). <a href="https://link.springer.com/article/10.1007/BF00139635" rel="nofollow noreferrer">https://link.springer.com/article/10.1007/BF00139635</a></li>
</ul>

CC BY-SA 4.0
2022-03-09T02:44:14.677Z
Thanks for your answer. I am interested in 2-clques (defined in [this youtube video](https://www.youtube.com/watch?v=LqPHg9uNp-o) by Wrath of Math). Sorry for confusing 2-cliques with 2-clubs.
Cyriac Antony
CC BY-SA 4.0
2022-03-09T02:58:12.523Z
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.
Cyriac Antony
CC BY-SA 4.0
2022-03-09T04:02:25.627Z
The name 2-clique is used in Mokken (Cliques, clubs and clans) as well.
Cyriac Antony
CC BY-SA 4.0
2022-03-09T06:39:42.447Z
@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
CC BY-SA 4.0
2022-03-09T00:19:58.253Z
2022-03-09T06:34:19.993Z
2022-03-09T06:34:19.993Z
JimN
<p>A 2-stable set (or a distance-two independent set) of a graph <span class="math-container">$G$</span> is a set of vertices which are pairwise at a distance greater than 2 in <span class="math-container">$G$</span>.</p>
<p><strong>Is there a name for a set of vertices which are pairwise at a distance at most 2?</strong></p>
<p>Such a set for a graph <span class="math-container">$G$</span> is basically a clique in the square graph <span class="math-container">$G^2$</span> of G.  Are there any papers that study (or at least mention) this parameter?</p>
<p>Update (2022-03-09):<br />
A set of vertices <span class="math-container">$S$</span> in a graph <span class="math-container">$G$</span> such that <span class="math-container">$d_G(u,v)\leq 2$</span> for all <span class="math-container">$u,v\in S$</span> is called a <strong>'2-clique'</strong> in <span class="math-container">$G$</span> (2nd definition here: [1]; usual meaning of <span class="math-container">$k$</span>-clique is a clique of size <span class="math-container">$k$</span>). Another related concept is that of a <em>2-club</em> (also called 2-clan). A 2-club in <span class="math-container">$G$</span> is a set of vertices <span class="math-container">$S$</span> in <span class="math-container">$G$</span> such that <span class="math-container">$d_{G[S]}(u,v)\leq 2$</span> for all <span class="math-container">$u,v\in S$</span> [2]. I am interested in '2-cliques', not 2-clubs. A clique in <span class="math-container">$G^2$</span> is a '2-clique', not a <em>2-club</em>. Thanks to JimN for directing me to the youtube channel <a href="https://www.youtube.com/channel/UCyEKvaxi8mt9FMc62MHcliw" rel="nofollow noreferrer">Wrath of Math</a> and thus to [1].</p>
<p>[1] <a href="https://www.youtube.com/watch?v=LqPHg9uNp-o" rel="nofollow noreferrer">https://www.youtube.com/watch?v=LqPHg9uNp-o</a><br />
[2] <a href="https://www.youtube.com/watch?v=hw3VJCTgnIA" rel="nofollow noreferrer">https://www.youtube.com/watch?v=hw3VJCTgnIA</a></p>

CC BY-SA 4.0
2022-03-07T13:10:52.510Z
Perhaps: The vertex set of a subgraph with diameter at most $2$.
Gamow
CC BY-SA 4.0
2022-03-08T01:38:54.287Z
Subgraph of diameter 2 is exactly what I am interested in. In [this question](https://math.stackexchange.com/q/4100618/120721), they call such maximal subgraphs as diameter-2 clques.
Cyriac Antony
CC BY-SA 4.0
2022-03-09T03:06:27.720Z
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$.
Cyriac Antony
<reference-request><graph-theory>
Name for set of vertices that are pairwise within distance two
Cyriac Antony
# Name for set of vertices that are pairwise within distance two

(Asked by: username_0 on 2022-03-07)

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](https://www.youtube.com/channel/UCyEKvaxi8mt9FMc62MHcliw) and thus to [1].

[1] <https://www.youtube.com/watch?v=LqPHg9uNp-o>  
[2] <https://www.youtube.com/watch?v=hw3VJCTgnIA>

**Tags:** reference-request, graph-theory
> **Comments:**
> **username_1**: Perhaps: The vertex set of a subgraph with diameter at most $2$.  
> **username_0**: Subgraph of diameter 2 is exactly what I am interested in. In [this question](https://math.stackexchange.com/q/4100618/120721), they call such maximal subgraphs as diameter-2 clques.  
> **username_0**: 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$.  

---

## 1 answers

### Answer by username_2 on 2022-03-09. Score: 1

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.

* Mokken, Cliques, clubs and clans, Quality and Quantity volume 13, pages161–173 (1979). <https://link.springer.com/article/10.1007/BF00139635>

> **Comments:**
> **username_0**: Thanks for your answer. I am interested in 2-clques (defined in [this youtube video](https://www.youtube.com/watch?v=LqPHg9uNp-o) by Wrath of Math). Sorry for confusing 2-cliques with 2-clubs.  
> **username_0**: 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.  
> **username_0**: The name 2-clique is used in Mokken (Cliques, clubs and clans) as well.  
> **username_2**: @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)  

---

