Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
It's formulated by extending threshold graphs. Given a threshold graph $(C,I)$ where $C$ is the clique and $I$ is the independent set, my extension is as follows: Each vertex $v\in I$ can be replaced by a new clique $K_v$ such that the vertices of $K_v$ have the same neighbors of $v$.
I guess this should have been studied, but it is hard to search such thing in graphclasses.org.
I believe that these are exactly the ($C_4$, $P_4$, $2P_3$)-free graphs — that is, the graphs whose induced subgraphs do not include 4-cycles, 4-vertex paths, or the graphs formed from the disjoint union of two 3-vertex paths. This class seems to lie between the threshold graphs themselves, which may be characterized as the ($C_4$, $P_4$, $2K_2$)-free graphs, and the trivially perfect graphs (intersections of nested intervals), which may be characterized as the ($C_4$, $P_4$)-free graphs. I don't think it has a name; at least, it doesn't seem to be listed at graphclasses.org.
To see that this is the correct characterization, consider the representation of trivially perfect graphs as the transitive closures of rooted forests. A forest gives rise to a (connected) threshold graph if and only if it has a directed path that contains all non-leaf nodes: adding a new isolated vertex corresponds, in the forest, to adding a new single-node tree, which doesn't change this property, and adding a new vertex connected to all of the others corresponds to adding a new root connected to all the previous tree roots, which again doesn't change this property (the new root can be part of the path).
Now your clique-replacement operation corresponds, in the tree view of a trivially perfect graph, to subdividing tree edges into paths (or replacing a one-vertex tree by a path). The forests that you can get from this operation are the ones in which there is a single directed path that contains all nodes with two or more children. A forest has such a path if and only if it does not have two unrelated forks (nodes with two or more children, neither of which can reach each other). And the subgraph you get in your trivially perfect graph when there are two forks is exactly $2P_3$.
The graphs whose complements are in the class you ask about — that is, the ($2K_2$,$P_4$,co-$2P_3$)-free graphs — were studied by Gurski, who showed that they are the same as the graphs of linear clique-width at most two. See theorem 10 of Gurski, Frank, "Characterizations for co-graphs defined by restricted NLC-width or clique-width operations", Discrete Math. 306 (2006), no. 2, 271–277.
