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.

$\endgroup$
3
  • $\begingroup$ Is it the join of $\overline{K_{k+1}}$ and $K_k$? I doubt if there is a name. $\endgroup$ Sep 15 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$ Sep 15 at 13:50
  • $\begingroup$ @PeterTaylor Right, my mistake. I still doubt if there's a name. $\endgroup$ Sep 15 at 13:59
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.

$\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 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.

$\endgroup$
1
  • $\begingroup$ Thanks for the comments and the nice references :) . $\endgroup$
    – GA316
    Sep 16 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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