3
$\begingroup$

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].

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

$\endgroup$
3
  • $\begingroup$ Perhaps: The vertex set of a subgraph with diameter at most $2$. $\endgroup$
    – Gamow
    Mar 7 at 13:10
  • 1
    $\begingroup$ Subgraph of diameter 2 is exactly what I am interested in. In this question, they call such maximal subgraphs as diameter-2 clques. $\endgroup$ Mar 8 at 1:38
  • $\begingroup$ 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$. $\endgroup$ Mar 9 at 3:06

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Mar 9 at 2:44
  • $\begingroup$ 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. $\endgroup$ Mar 9 at 2:58
  • $\begingroup$ The name 2-clique is used in Mokken (Cliques, clubs and clans) as well. $\endgroup$ Mar 9 at 4:02
  • 1
    $\begingroup$ @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) $\endgroup$
    – JimN
    Mar 9 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.