Recognizing some corona products in polynomial time

• Jarlilson Guajajara UFG
• Julliano Rosa Nascimento UFG

DOI: https://doi.org/10.5753/erigo.2024.4861

Resumo

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.

Palavras-chave: corona product, graphs, algorithm, hierarchical networks, isomorphism

Referências

Bhange, A. and Bhapkar, H. (2020). Perfect coloring of corona product of cycle graph with cycle, path and null graph. Advances in Mathematics: Scientific Journal, 9:10839–10844.

Bondy, J. A. and Murty, U. S. R. (2008). Graph theory. Springer Publishing Company, Incorporated.

Booth, K. S. and Colbourn, C. J. (1979). Problems polynomially equivalent to graph isomorphism. Technical Report CS-77-04, Department of Computer Science, University of Waterloo.

Colbourn, C. (1981). On testing isomorphism of permutation graphs. Networks, 11(1):13–21.

da Silva, D. and da Silva, H. (2022). Algoritmos para compor uma ferramenta web: geração de grafos grades e cordais e solução de conjunto independente, clique e emparelhamento em grafos. In Anais da X Escola Regional de Informática de Goiás, pages 118–129, Porto Alegre, RS, Brasil. SBC.

Feigenbaum, J. and Schaffer, A. (1985). Recognizing corona graphs. AT&T Bell Laboratories Technical Memorandum.

Frucht, R. and Harary, F. (1970). On the corona of two graphs. Aequationes mathematicae, 4(3):322–325.

Furmanczyk, H., Kubale, M., and Mkrtchyan, V. (2012). Equitable colorings of corona multiproducts of graphs. Discussiones Mathematicae Graph Theory, 37.

G. Yero, I., Kuziak, D., and Aguilar, A. (2012). Coloring, location and domination of corona graphs. Aequationes Mathematicae.

Graph problems tool (2022). Graph problems tool. [link]. Accessed on October 13, 2024.

Halim, S. (2015). Visualgo–visualising data structures and algorithms through animation. Olympiads in informatics, 9:243–245.

Sabidussi, G. (1959). The composition of graphs. Duke Mathematical Journal, 26(4):693 – 696.

Sharma, R., Adhikari, B., and Krueger, T. (2019). Self-organized corona graphs: A deterministic complex network model with hierarchical structure. Advances in Complex Systems, 22(06):1950019.

Silva, B. R. (2018). Algoritmos e limites para os números envoltório e de Carathéodory na convexidade P3. Dissertação (mestrado em ciência da computação), Universidade Federal de Goiás, Goiânia. 93 f.

UnickSoft (2024). Graph online. [link]. Accessed on October 12, 2024.