1
$\begingroup$

A join of two graphs is the union of both graphs with additional edges such that every vertex of the first graph is connected to every vertex of the second graph. There is a generalization of this, which I will call the $G$-join. For a given graphs $G$ and $G_1, G_2 \cdots G_{v}$, where $v$ is the number of vertices in $G$, the $G$-join of the graphs is the union of all of them such that every vertex of $G_u$ is connected to every vertex of $G_v$ if there is an edge between $u$ and $v$ in $G$. So the original graph join is just a $P_2$-join.

How fast can we recognize whatever a graph is $G$-join? What if we fix $G$ to a specific graph?

The only algorithm I could think of is the obvious one, iterate over all partitions and check the edges.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.