Timeline for If a vertex belongs to many maximal cliques, does it belong to a large star?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 17, 2020 at 4:40 | comment | added | Quotable | @user36212 Yes, you are right. I actually came across an even more extreme example when investigating this question: Suppose $|V(G)| = n$ is divisible by 3 (for simplicity). Then consider the Turan graph $T(n, n/3)$. Then this is a complete multipartite graph with $n$ stable sets of size 3. Attaching a vertex $v$ adjacent to all vertices in $T(n, n/3)$ then makes $v$ have a largest star of size 3, but who belongs to $3^{n/3}$ maximal cliques. This is in fact as bad as it possibly can get (see the paper Moon and Moser, "On Cliques in Graphs"). | |
| May 17, 2020 at 4:34 | comment | added | Quotable | @WlodAA I agree with the sentiment of what you say; however, when I asked this question, I did not yet have an answer. When I cam upon an answer, I thought I would share the results of this with others who may be interested in the answer | |
| May 16, 2020 at 14:33 | comment | added | user36212 | Can be much worse. Take a complete graph on mn+1 vertices for your favourite m,n, let v be one vertex and remove the edges of a collection of m disjoint n-cliques avoiding v. The largest induced star centred at v has n leaves, but v is in n^m maximal cliques. | |
| May 16, 2020 at 3:26 | comment | added | Wlod AA | To ask a question when you already have an answer is against the spirit of this Q&A group. Thus, I stilled "plused-1" you here but not the question. Please, next time avoid this kind of combination. | |
| May 16, 2020 at 3:21 | comment | added | Wlod AA | Perhaps $\ 2\cdot n\,$? | |
| Apr 16, 2020 at 2:01 | history | answered | Quotable | CC BY-SA 4.0 |