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

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 contribut...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Haviar,M., Kurtulík,S.
Lenguaje:	English
Publicado:	Universidad de La Frontera. Departamento de Matemática y Estadística. 2021
Materias:	graph graceful labelling graph chessboard labelling sequence labelling relation
Acceso en línea:	http://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0719-06462021000200313
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:scielo:S0719-06462021000200313
record_format	dspace
spelling	oai:scielo:S0719-064620210002003132021-08-18A new class of graceful graphs: k-enriched fan graphs and their characterisationsHaviar,M.Kurtulík,S. graph graceful labelling graph chessboard labelling sequence labelling relation 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.info:eu-repo/semantics/openAccessUniversidad de La Frontera. Departamento de Matemática y Estadística.Cubo (Temuco) v.23 n.2 20212021-08-01text/htmlhttp://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0719-06462021000200313en10.4067/S0719-06462021000200313
institution	Scielo Chile
collection	Scielo Chile
language	English
topic	graph graceful labelling graph chessboard labelling sequence labelling relation
spellingShingle	graph graceful labelling graph chessboard labelling sequence labelling relation Haviar,M. Kurtulík,S. A new class of graceful graphs: k-enriched fan graphs and their characterisations
description	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.
author	Haviar,M. Kurtulík,S.
author_facet	Haviar,M. Kurtulík,S.
author_sort	Haviar,M.
title	A new class of graceful graphs: k-enriched fan graphs and their characterisations
title_short	A new class of graceful graphs: k-enriched fan graphs and their characterisations
title_full	A new class of graceful graphs: k-enriched fan graphs and their characterisations
title_fullStr	A new class of graceful graphs: k-enriched fan graphs and their characterisations
title_full_unstemmed	A new class of graceful graphs: k-enriched fan graphs and their characterisations
title_sort	new class of graceful graphs: k-enriched fan graphs and their characterisations
publisher	Universidad de La Frontera. Departamento de Matemática y Estadística.
publishDate	2021
url	http://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0719-06462021000200313
work_keys_str_mv	AT haviarm anewclassofgracefulgraphskenrichedfangraphsandtheircharacterisations AT kurtuliks anewclassofgracefulgraphskenrichedfangraphsandtheircharacterisations AT haviarm newclassofgracefulgraphskenrichedfangraphsandtheircharacterisations AT kurtuliks newclassofgracefulgraphskenrichedfangraphsandtheircharacterisations
_version_	1714206812012544000

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

Ejemplares similares