A new class of graceful graphs: k-enriched fan graphs and their characterisations

• Autores: Miroslav Haviar, S. Kurtulík
• Localización: Cubo: A Mathematical Journal, ISSN 0716-7776, ISSN-e 0719-0646, Vol. 23, Nº. 2, 2021, págs. 313-331
• Idioma: inglés
• DOI: 10.4067/S0719-06462021000200313
• Enlaces
  • Texto completo
• Resumen
  • español

    RESUMEN La Conjetura del Árbol Amable enunciada por Rosa a mediados de los 1960s dice que cada Árbol puede ser etiquetado amablemente. Es uno de los problemas abiertos mejor conocidos en Teoría de Grafos. La conjetura ha causado un gran interés en el estudio de la amabilidad de grafos simples y ha llevado a muchas contribuciones nuevas a la lista de grafos amables. De todas formas, debe reconocerse que no se sabe mucho acerca de la estructura de grafos amables tras 55 años. Nuestro artículo añade una familia infinita de clases de grafos amables a la lista de grafos amables simples conocidos. Introducimos clases de grafos abanico k-enriquecidos kFn para todos los enteros k; n ≥ 2 y demostramos que estos grafos son amables. Más aún, entregamos caracterizaciones de los grafos abanico k-enriquecidos kFn entre todos los grafos simples vía sucesiones de etiquetado de Sheppard introducidas en los 1970s, y también a través de relaciones de etiquetados y tableros de ajedrez de grafos. Estos últimos acercamientos son herramientas nuevas para el estudio de grafos amables introducidos por Haviar e Ivaška en 2015. Las relaciones de etiquetado están relacionadas cercanamente con las sucesiones de etiquetado de Sheppard mientras que los tableros de ajedrez de grafos proveen una linda visualización de etiquetados amables. Concluimos nuestro artículo con un problema abierto relacionado con otra familia infinita de grafos abanico extendidos.

  • English

    ABSTRACT The Graceful Tree Conjecture stated by Rosa in the mid 1960s says that every tree can be gracefully labelled. It is one of the best known open problems in Graph Theory. The conjecture has caused a great interest in the study of gracefulness of simple graphs and has led to many new contributions to the list of graceful graphs. However, it has to be acknowledged that not much is known about the structure of graceful graphs after 55 years. Our paper adds an infinite family of classes of graceful graphs to the list of known simple graceful graphs. We introduce classes of k-enriched fan graphs kFn for all integers k, n ≥ 2 and we prove that these graphs are graceful. Moreover, we provide characterizations of the k-enriched fan graphs kFn among all simple graphs via Sheppard's labelling sequences introduced in the 1970s, as well as via labelling relations and graph chessboards. These last approaches are new tools for the study of graceful graphs introduced by Haviar and Ivaška in 2015. The labelling relations are closely related to Sheppard's labelling sequences while the graph chessboards provide a nice visualization of graceful labellings. We close our paper with an open problem concerning another infinite family of extended fan graphs.

• Referencias bibliográficas
  • Amutha, S.,Uma Devi, M.. (2019). Super Graceful Labeling for Some Families of Fan Graphs. Journal of Computer and Mathematical Sciences. 10....
  • Gallian, J. A.. (2019). A Dynamic Survey of Graph Labeling. Electron. J. Combin..
  • Gardner, M.. (1972). Mathematical Games: The graceful graphs of Solomon Golomb. Sci. Am.. 226. 108
  • Golomb, S. W.. (1972). Graph Theory and Computing. Academic Press.
  • Haviar, M.,Ivaška, M.. (2015). Vertex Labellings of Simple Graphs. Heldermann-Verlag. Lemgo, Germany.
  • Hrnčiar, P.,Haviar, A.. (2001). All trees of diameter five are graceful. Discrete Math.. 233. 133
  • Ivaška, M.. (2009). Student Competition ŠVOČ. M. Bel University. Banská Bystrica.
  • (2020). Graceful labellings of graphs. Department of Mathematics, M. Bel University. Banská Bystrica.
  • Rosa, A.. (1965). O cyklických rozkladoch kompletného grafu" (On cyclic decompositions of the complete graph). Československá akadémia...
  • Rosa, A.. (1967). On certain valuations of the vertices of a graph. Theory of Graphs (Internat. Symposium. Rome. July 1966.
  • Sheppard, D. A.. (1976). The factorial representation of major balanced labelled graphs. Discrete Math.. 15. 379
  • Xu, K.,Li, X.,Klavžar, S.. (2018). On graphs with largest possible game domination number. Discrete Math.. 341. 1768