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
    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
    Sep 15, 2021 at 13:50
  • $\begingroup$ @PeterTaylor Right, my mistake. I still doubt if there's a name. $\endgroup$
    – Brendan McKay
    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
    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
    Sep 16, 2021 at 12:47

Your Answer

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

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