# "Gluing and copy" graphs

Consider the minimal class of (simple, undirected) connected graphs (strictly speaking, isomorphism classes of connected graphs) which contains a single vertex $$K_1$$, and is closed under following operations:

1. add a copy $$\tilde{v}$$ of a vertex $$v$$ (neighbours of the new vertex are the same as of $$v$$) and do not join it with $$v$$ (the new graph must be connected, in other words, you are not allowed to start with this operation applied to $$K_1$$);

2. add a copy $$\tilde{v}$$ of a vertex $$v$$ (neighbours of the new vertex are the same as of $$v$$) and join it with $$v$$;

3. glue two graphs by a vertex.

Alternative description of this class (I hope that we have a proof, it is not very short) is the following: any simple cycle with at least 5 vertices must have two disjoint chords.

Was such class studied?

• Possibly interesting connection: by your alternative description, this class contains the distance-hereditary graphs (which can be characterised as those graphs such that every cycle with $\geq 5$ vertices has at least two 'crossing' chords). en.wikipedia.org/wiki/Distance-hereditary_graph Jun 16, 2022 at 13:18
• @ThomasBloom Oh, it seems to be exactly the same class of graphs Jun 16, 2022 at 13:25
• Ah yes, so it is! Neat. Jun 16, 2022 at 13:29
• @ThomasBloom would you please post this as an answer, to make the post answered? Jun 16, 2022 at 13:40

This is the same as the class of distance-hereditary graphs, which have received a fair amount of attention (see https://en.wikipedia.org/wiki/Distance-hereditary_graph).

There is a fantastic website called Information System on Graph Classes and their Inclusions at graphclasses.org. "ISGCI is an encyclopaedia of graphclasses" with a lot of information on definitions, equivalences, inclusions, algorithms, etc about graph classes that are closed under induced subgraphs.

For example, one can find the class in your question by searching for cycle chords. There are 8 results, including seemingly the correct one: Graphclass: (5,2)-crossing-chordal. On this page, one can learn that this class is equivalent to distance-hereditary as you have already learned.

It is also equivalent to HHDG-free, which unfortunately lacks a definition but should say (house, hole, domino, gem)-free. (Note that house, domino, and gem are individual graphs, while hole is a parametrized family.) This equivalence could be useful for your purposes, for example if you want a "forbidden induced subgraph" characterization of your class.

[Note that the search suggested above also finds Meyniel graphs, which are graphs in which "every cycle of odd length at least 5 has at least 2 chords". These are also known as very strongly perfect graphs. It seems that in your characterization, you use the word simple to end up with the other class?]

In this case, of course the Wikipedia page on distance-hereditary graphs is very detailed (including a definition of "HHDG-free"), but perhaps this site may be helpful to you or others in the future! It is often useful in a very similar way to The On-Line Encyclopedia of Integer Sequences (OEIS).

This class is the same as the $$\Delta$$-confluent graphs introduced by Eppstein, Goodrich, and Meng (Delta-confluent Drawings). It is easy to see that $$\Delta$$-confluent graphs are closed under the operations you allow (and a single vertex is $$\Delta$$-confluent), and all $$\Delta$$-confluent graphs can be built using these operations (easy induction).

Eppstein, Goodrich, and Meng also prove that the $$\Delta$$-confluent graphs are the same as the distance-hereditary graphs, so the result follows from that.

Theorem 2 in the Eppstein, Goodrich, and Meng paper is the result tying distance-heredity to the operations you allow. It's attributed to a 1986 paper by H. Bandelt and H. M. Mulder. Distance-hereditrary graphs.