Recognizing some corona products in polynomial time - Guajajara, Jarlilson; Nascimento, Julliano Rosa (Anais da Escola Regional de Informática de Goiás (ERI-GO); 2024: Anais da XII Escola Regional de Informática de GoiásDO - 10.5753/erigo.2024.4861, 2024)
The corona product of G and H is the graph G◦H, obtained by taking a copy of G, |V (G)| copies of H, and connecting the i-th vertex of G to each vertex in the i-th copy of H, where 1 ≤ i ≤ |V (G)|. We present an algorithm for recognizing some corona product graphs, a structure that is particularly useful for analyzing hierarchical networks. Our results demonstrate that the algorithm works for arbitrary graphs G when H is restricted to classes where the isomorphism problem is solvable in polynomial time. Notably, for H as a path, cycle, or complete graph, the algorithm runs in cubic time.