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

Improve this question
$\endgroup$
3
  • $\begingroup$ Perhaps: The vertex set of a subgraph with diameter at most $2$. $\endgroup$
    – Gamow
    Mar 7, 2022 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$
    – Cyriac Antony
    Mar 8, 2022 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$
    – Cyriac Antony
    Mar 9, 2022 at 3:06

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Cyriac Antony
    Mar 9, 2022 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$
    – Cyriac Antony
    Mar 9, 2022 at 2:58
  • $\begingroup$ The name 2-clique is used in Mokken (Cliques, clubs and clans) as well. $\endgroup$
    – Cyriac Antony
    Mar 9, 2022 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, 2022 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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