Define A Graph - Tree Graph With "Cycles" as Nodes

676 Views Asked by At

I am working on my thesis and I would like to have a proper definition for this type of graph: "Tree Graph With Nodes As Cycles"

I would like to define a graph similar to a "simple tree", but some of its nodes are replaced with some cycles. The graph should be undirected, connected and have no multiple edges between any pair of nodes. The graph is somehow similar to the picture given. My question is how to give a formal definition for this type of graph?

Edited 1: Circles should have disjoint subset of vertices. I would like to add another example for clarifying the type of graph that I would like to define: Another Example

2

There are 2 best solutions below

2
On BEST ANSWER

A snappy definition of your object is "a connected graph in which every vertex is part of at most one cycle".

If cycles could touch and share up to one vertex, this would be a cactus graph. (Here, the condition is that every edge is part of at most one cycle.) Your graphs are a subclass of these, but with no existing terminology.

If you want a term, you might have to make something up. A cactus graph in which each vertex is part of at most two cycles is a Christmas cactus, according to the Wikipedia link above. You're looking for a condition that's one stricter than this condition, so perhaps it should be a Christmas Eve cactus?

Also quoting Wikipedia:

In topological graph theory, the graphs whose cellular embeddings are all planar are exactly the subfamily of the cactus graphs with the additional property that each vertex belongs to at most one cycle. These graphs have two forbidden minors, the diamond graph and the five-vertex friendship graph.

This doesn't name your family of graphs, but links to a paper where they're discussed further: https://doi.org/10.1016/0095-8956(72)90040-8.

3
On

How about this:

Call a graph $G$ an almost-tree iff (1) $V(G) = U_1+U_2+\ldots +U_m +W$ where the $U_i$s are disjoint sets of vertices of cardinality at least 3

(2) $G[U_i]$ is a cycle on $|U_i|$ vertices

(3) the resulting graph $f(G)$ formed by collapsing each $U_i$ to a single vertex $v_i$ and where there is an edge $v_iv_j$ [respectively, $v_iw$; $w \in W$] iff there is an edge in $G$ between a vertex in $U_i$ and $U_j$ [respectively, iff there is an edge in $G$ between a vertex in $U_i$ and $w$], is a tree.

(4) For all $i,j$ there is at most one edge between the vertices in $U_i$ and the vertices $U_j$, and for each $i$ and $w \in W$ there is at most one edge between the vertices in $U_i$ and $w$.

Note that given an almost-tree $G$, that the tree $f(G)$ is well-defined and unique. Call $\{U_1,\ldots, U_m, W\}$ the cycle-partitioning of the vertices of the almost-tree $G$. Note that this cycle-partitioning is well-defined and unique as well.

This is how I would do it.