2
$\begingroup$

Let $V$ be a set of $n$ vertices. Fix $3 \le k \le n$. Let $\binom V k$ be the set of all $k$ element subsets of $V$.

We add the edges in $V$ as follows: Let $\mathcal S \subseteq \binom V k$ be fixed. For each $F \in \mathcal S$, I am making the vertices in $F$ mutually adjacent. Let's call this graph $G_k(\mathcal S)$.

  1. I want to learn how the graph $G_k(\mathcal S)$ looks like?

  2. Is there any name for $G_k(\mathcal S)$ in the literature?

  3. Some references regarding these graphs.

Kindly share your thoughts. Thank you.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ This brings to mind the en.wikipedia.org/wiki/Clique_complex . In terms of this, every $1$-dimensional face (but not necessarily every $2$-dimensional face) is part of a face of dimension $k-1$. (I admit that does not sound very helpful.) $\endgroup$
    – Ville Salo
    Commented May 16, 2020 at 15:31
  • $\begingroup$ This seems a little broad, especially Q1. For example, every graph can arise with $k=2$. $\endgroup$
    – verret
    Commented May 16, 2020 at 21:59
  • 1
    $\begingroup$ Well, for a given $k$, the class of graph one gets is exactly the graphs such that every edge is contained in a $k$-clique. So for $k=3$, it's graphs such that every edge is in a triangle. $\endgroup$
    – verret
    Commented May 17, 2020 at 2:53
  • 1
    $\begingroup$ Especially in computer science / complexity theory, if we were to pick one size-$k$ subset, we would call this "planting a clique" in the graph. $\endgroup$
    – usul
    Commented May 17, 2020 at 5:29
  • 1
    $\begingroup$ I think that “graphs with every edge in a triangle” is the simplest description of this family, and that no significant or interesting alternative characterisations are widely known. I’ve considered regular graphs (quartic, more precisely) with this property and did not come across anything in general. $\endgroup$
    – Gordon Royle
    Commented May 17, 2020 at 13:02

0

Reset to default

You must log in to answer this question.