2
$\begingroup$

Let $G_k$ be the graph obtained by applying the following procedure k-times:

  1. Start with a graph with single vertex $v$ (Call this graph $H$)

  2. Add a vertex $u$ such that $u$ is not adjacent to any vertex of $H$ (i.e., $K:= H \cup \{u\}$) union of two graphs

  3. Add a vertex $w$ such that $w$ is adjacent to all the vertices of $K$ (i.e., $J := K \vee \{w\}$) join of two graphs

  4. Set $H = J$

  5. Goto step 2.

My question is, is there a name for the class of graphs $\{G_k\}_{k\ge1}$? Please provide some references. Thank you.

Improve this question
$\endgroup$
3
  • $\begingroup$ Is it the join of $\overline{K_{k+1}}$ and $K_k$? I doubt if there is a name. $\endgroup$
    – Brendan McKay
    Commented Sep 15, 2021 at 1:45
  • 1
    $\begingroup$ @BrendanMcKay, no. The initial vertex $v$ from step 1 and the $w$ vertices form $K_{k+1}$, and the $u$ vertices have degrees $1$ to $k$ because (indexing by iteration at which they're added) $u_i - w_j$ iff $i \le j$. $\endgroup$
    – Peter Taylor
    Commented Sep 15, 2021 at 13:50
  • $\begingroup$ @PeterTaylor Right, my mistake. I still doubt if there's a name. $\endgroup$
    – Brendan McKay
    Commented Sep 15, 2021 at 13:59

2 Answers 2

Reset to default
4
$\begingroup$

It's not quite the same question, but the graphs that can be obtained by repeating either of the two operations (add a disjoint vertex or a dominating vertex), not necessarily in strict alternation, are called threshold graphs.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. I am hearing this term for the first time :) . I will check the link and the iterature. Thanks again. $\endgroup$
    – GA316
    Commented Sep 16, 2021 at 12:47
3
$\begingroup$

As David Eppstein remarked, those graphs will all be threshold graphs. Moreover, they will be universal threshold graphs, in the sense that $G_k$ contains all threshold graphs on $k+1$ vertices. This is also discussed in Section 4.1.6 of Michael Engen's thesis.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the comments and the nice references :) . $\endgroup$
    – GA316
    Commented Sep 16, 2021 at 12:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .