

CUBO, A Mathematical Journal

Vol. 23, no. 02, pp. 313–331, August 2021

DOI: 10.4067/S0719-06462021000200313

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

M. Haviar1,2

S. Kurtuĺık1

1 Department of Mathematics,

Faculty of Natural Sciences, Matej

Bel University, Banská Bystrica,

Slovakia.

miroslav.haviar@umb.sk

kurtuliksamuel@gmail.com

2 Mathematical Institute, Slovak

Academy of Sciences, Bratislava,

Slovakia.

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 Ivaš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.

RESUMEN

La Conjetura del Árbol Amable enunciada por Rosa a mediados de los 1960s

dice que cada árbol puede ser etiquetado amablemente. Es uno de los proble-

mas abiertos mejor conocidos en Teoŕıa de Grafos. La conjetura ha causado

un gran interés en el estudio de la amabilidad de grafos simples y ha lle-

vado 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 años.

Nuestro art́ıculo añ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. Más aún, entregamos caracterizaciones de

los grafos abanico k-enriquecidos kFn entre todos los grafos simples v́ıa suce-

siones de etiquetado de Sheppard introducidas en los 1970s, y también a

través de relaciones de etiquetados y tableros de ajedrez de grafos. Estos

últimos acercamientos son herramientas nuevas para el estudio de grafos

amables introducidos por Haviar e Ivaška en 2015. Las relaciones de eti-

quetado están relacionadas cercanamente con las sucesiones de etiquetado

de Sheppard mientras que los tableros de ajedrez de grafos proveen una

linda visualización de etiquetados amables. Concluimos nuestro art́ıculo con

un problema abierto relacionado con otra familia infinita de grafos abanico

extendidos.

Keywords and Phrases: graph, graceful labelling, graph chessboard, labelling sequence, labelling relation.

2020 AMS Mathematics Subject Classification: 05C78

Accepted: 10 June, 2021

Received: 19 February, 2021

©2021 M. Haviar et al. This open access article is licensed under a Creative Commons

Attribution-NonCommercial 4.0 International License.

http://cubo.ufro.cl/
http://dx.doi.org/10.4067/S0719-06462021000200313
https://orcid.org/0000-0002-9721-152X


314 M. Haviar & S. Kurtuĺık CUBO
23, 2 (2021)

1 Introduction

A simple graph of size m has a graceful labelling, and it is said to be graceful, when its vertices can

be assigned different labels from the set {0, 1, ...,m} such that the absolute values of the differences
in vertex labels of edges form the set {1, ...,m}. The Graceful Tree Conjecture stated by Rosa in
[9] and [10] says that every tree is graceful. The conjecture has now been open for more than a

half century and is one of the most attractive open problems in Graph Theory. The best source of

information on attacks of the conjecture and on the study of labellings of graphs is the electronic

book by Gallian [2].

Still, not much is known about the structure of graceful graphs. One of the known results, due to

Hrnčiar and Haviar [6], is that all trees of diameter five are graceful.

The Graceful Tree Conjecture has led to a much increased interest in the study of gracefulness

of simple graphs. In this paper we introduce a new infinite family of classes of simple graphs, k-

enriched fan graphs kFn, for all integers k,n ≥ 2, and we show that they are graceful. These classes
of graphs have been recently considered in the second author’s MSc thesis [8]. The k-enriched fan

graphs kFn are a natural generalisation of the class of fan graphs Fn, which were shown to be

graceful in [5].

For a better understanding of the general k-enriched fan graphs and their characterisations, the

special cases k = 2 and k = 3 of double and triple fan graphs are dealt with separately. Char-

acterisations of the double and triple fan graphs, and then of the k-enriched fan graphs, are

presented using the tools of labelling sequences, labelling relations and graph chessboards. La-

belling sequences were introduced in 1976 by Sheppard in [11] while the labelling relations and

graph chessboards as new tools for the study of graceful graphs were introduced and studied rather

recently by Haviar and Ivaška in [5].

The basic terms and facts needed in this paper are presented in Section 2. This includes the

concepts of labelling sequences, labelling relations and graph chessboards. In Section 3 we describe

fan graphs and their graceful labellings from [5]. Then we generalise the concept of a fan graph

to the one called a double fan graph resp. triple fan graph by connecting n paths P2 resp. P3 to

the main path of a given fan graph Fn. We construct for these graphs their graceful labellings

and describe them by the corresponding labelling sequences, the labelling relations and the graph

chessboards. Finally we study the general case of the k-enriched fan graphs kFn for any integers

k,n ≥ 2. These graphs contain, compared to the classic fan graphs Fn, n copies of the star Sk
connected to the main path Pn. Again, we construct for these graphs their graceful labellings and

characterize them by their labelling sequences, the labelling relations and the graph chessboards.

We conclude the paper with proposing another natural extension of the class of fan graphs and

raising an open problem whether these extended fan graphs can be shown to be graceful and


CUBO
23, 2 (2021)

A new class of graceful graphs: k-enriched fan graphs 315

characterized in the manner presented here.

2 Preliminaries

In this section we recall the necessary basic terms concerning graph labellings as well as the

concepts of labelling sequences, labelling relations and simple chessboards, which we use as our

tools to describe new classes of graceful graphs. These definitions are taken primarily from [10]

and [5].

In this paper we study only finite simple graphs, that is, finite unoriented graphs without loops

and multiple edges. The following concept was called valuation by Rosa in his seminal paper [10].

Definition 2.1 ([10, 5]). A vertex labelling (or labelling for short) f of a simple graph G = (V,E)

is a one-to-one mapping of its vertex set V(G) into the set of non-negative integers assigning to

the vertices so-called vertex labels.

By the label of an edge uv in the labelling f we mean the number |f(u) −f(v)|, where f(u),f(v)
are the vertex labels of u,v. In this text we will denote by f(VG) the set of all vertex labels and

by f(EG) the set of all edge labels in the labelling f of a graph G.

Several types of graph labellings are known, e.g. α,β,σ,ρ, which have become very well-known

since the publication of Rosa’s paper [10] in 1967, and further γ,δ,p,q introduced by Rosa in his

dissertation thesis [9] in 1965. In this text we study only β-labellings called graceful labellings.

Definition 2.2 ([10, 5]). A graceful labelling (or β-labelling) of a graph G = (V,E) of size m is a

vertex labelling with the following properties:

(1) f(VG) ⊆{0, 1, . . . ,m}, and

(2) f(EG) = {1, 2, . . . ,m}.

The term graceful was given to β-labellings in 1972 by Golomb [4] and its immediate use was

enhanced by a popularization by Gardner [3]. Hence a graceful labelling of a graph of size m has

vertex labels among the numbers 0, 1, ...,m such that the induced edge labels are different and

cover all values 1, 2, ...,m. In Figure 1 we can see some graceful graphs.

Each graceful graph can be represented by a sequence of non-negative integers. This was shown

by Sheppard in [11] where he introduced the concept of a labelling sequence as follows:

Definition 2.3 ([11, 5]). For a positive integer m, a labelling sequence is the sequence of non-

negative integers (j1,j2, . . . ,jm), denoted (ji), where

0 ≤ ji ≤ m− i for all i ∈{1, 2, . . . ,m}. (LS)


316 M. Haviar & S. Kurtuĺık CUBO
23, 2 (2021)

0 1

3

0 4

3 2

1

3

0

65

4 2

Figure 1: Some graceful graphs

Sheppard also proved that there is a one-to-one correspondence between graceful labellings of

graphs (without isolated vertices) and labelling sequences. Therefore we can understand labelling

sequences as a tool to encode graceful labellings of graphs. The connection is described in the

following theorem.

Theorem 2.4 ([11, 5]). There exists a one-to-one correspondence between graphs of size m having

a graceful labelling f and between labelling sequences (ji) of m terms. The correspondence is given

by

ji = min{f(u),f(v)}, i ∈{1, 2, . . . ,m},

where u,v are the end-vertices of the edge labelled i.

Now we recall the definition of a labelling relation. It is another tool to describe gracefully labelled

graphs, which is closely related to the labelling sequence. The concept of the labelling relation was

introduced and studied in [5].

Definition 2.5 ([5]). Let L = (j1,j2, . . . ,jm) be a labelling sequence. Then the relation A(L) =

{[ji,ji + i], i ∈{1, 2, . . . ,m}} is called a labelling relation assigned to the labelling sequence L.

To visualize a labelling relation and also a labelling sequence we will use a labelling table (see

Figure 2). A table is formed by using the numbers 1, 2, ...,m as headers for the columns, followed

by two rows. The first row contains the numbers from the labelling sequence and the second row

contains the sums of the corresponding numbers from the heading and from the first row. The

pairs from first and second row in each column are then the elements of the labelling relation (and

correspond to the edges of the graph).

1 2 3 . . . m

j1 j2 j3 . . . jm
j1 + 1 j2 + 2 j3 + 3 . . . jm + m

Figure 2: Displaying a labelling table

Example 2.6. In Figure 3 we can see the labelling table assigned to the labelling sequence (5, 4, 3, 2, 1, 0)

and its graceful graph whose edges correspond to the elements of the labelling relation.


CUBO
23, 2 (2021)

A new class of graceful graphs: k-enriched fan graphs 317

1 2 3 4 5 6

5 4 3 2 1 0
6 6 6 6 6 6

0

12

3

4 5

6

Figure 3: Example of a labelling table and its corresponding graceful graph

Every labelled simple graph of order n can be represented by a chessboard, i.e. a table with n rows

and n columns, where every edge labelled uv is represented by a pair of dots with coordinates [u,v]

and [v,u]. This idea of visualization of vertex labellings of graphs by chessboards and independent

discoveries of similar ideas are described in [5, Chapter 2]. One can also obtain such a graph

chessboard by taking the adjacency matrix of a graph and placing dots in the cells corresponding

to “ones” in the matrix while leaving the cells corresponding to “zeros” in the matrix empty (cf. [5,

p. 25]).

Several types of graph chessboards like simple chessboards, double chessboards, M-chessboards,

dual chessboards and twin chessboards were studied by Haviar and Ivaška in [5]. In this text we

0

6 7

2

5

9 3

Figure 4: Example of a graph of size m = 9 and its corresponding simple chessboard

use only the idea of a simple chessboard, which is a useful tool in the visualization of gracefully

labelled graphs.

For a positive integer m consider an (m + 1) × (m + 1)-table. Rows are numbered by 0, 1, ...,m
from the top to the bottom and columns are numbered by 0, 1, ...,m from the left to the right as

shown in Figure 4. The cell with coordinates [i,j] of the table will mean the cell in the i-th row

and the j-th column. The r-th diagonal in the table is the set of all cells with coordinates [i,j]

where i − j = r and i ≥ j. The main diagonal is the 0-th diagonal in the table and all other
diagonals are called associate diagonals.

To a graph of size m whose vertices are labelled by different numbers from the set {0, 1, 2, ...,m}


318 M. Haviar & S. Kurtuĺık CUBO
23, 2 (2021)

we assign its simple chessboard as the (m + 1) × (m + 1)-table described above such that every
edge labelled uv in the graph is represented by a pair of dots in the cells with coordinates [u,v]

and [v,u]. It follows that the simple chessboards are symmetric about the main diagonal. An

illustration of the simple chessboard of such a labelled graph of size 9 is in Figure 4.

If there is exactly one dot on each of the associate diagonals, then the simple chessboard will be

called graceful as it clearly encodes a graceful graph. We can see a gracefully labelled graph of size

8 and its graceful simple chessboard in Figure 5.

0 8 1

4 7

3 5 2

Figure 5: Gracefully labelled graph and its corresponding graceful simple chessboard

3 Fan graphs and their descriptions

A fan graph is a join of a path and a single vertex K1. (See [5, Section 4.4.7] and Figure 6.) Its

“bottom part” is formed by a star.

In this text we introduce the notation Fn for a fan graph whose main path is Pn. We obviously

require n ≥ 2 in order to have the shape of “a fan”. The fan graph Fn thus has order n + 1 and
size 2n − 1. In Figure 6 we can see a gracefully labelled fan graph F8 of size 15, with the main
path P8, its corresponding simple chessboard and its labelling relation.

The following two results taken from [5] characterize fan graphs via their labelling sequences,

labelling relations and simple chessboards. (It is important to notice that [5, Section 4.4.7] considers

the fan graphs that are Fn+1 in our present notation. In Figure 4.10 there we have the fan graph

F7 with considering n = 6. That is why for our graphs G studied in [5, Section 4.4.7] we talk about

their size m = 2n + 1.) The notation N in the next theorem and in our subsequent results is used,

as in [5], for the set of all positive integers and the notation bxc is used for the largest integer not
greater than x (the floor function).

Theorem 3.1 ([5]). Let G be a graph of size m = 2n + 1 for some n ∈ N. Then G is a fan graph


CUBO
23, 2 (2021)

A new class of graceful graphs: k-enriched fan graphs 319

0 7 1 6 2 5 3 4

15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

3 3 2 2 1 1 0 7 6 5 4 3 2 1 0
4 5 5 6 6 7 7 15 15 15 15 15 15 15 15

Figure 6: Representations of the gracefully labelled fan graph F8

if and only if there exists a labelling sequence (j1,j2, . . . ,jm) of G such that

ji =



⌊
n−i+1

2

⌋
, if i ≤ n,

m− i, if i > n.
(LSFG)

Corollary 3.2 ([5]). Let G be a graph of size m = 2n + 1 that can be gracefully labelled and let L
be the set of all its labelling sequences. Then the following are equivalent:

(a) G is a fan graph.

(b) There exists a labelling sequence L ∈L which satisfies (LSFG).

(c) For some L ∈L, the labelling relation is

A(L) ={[i,n− 1] | i ∈{0, 1, . . . ,
⌊
n−i

2

⌋
}}∪

{[i,n− i + 1] | i ∈{0, 1, . . . ,
⌊
n
2

⌋
}}∪

{[i,m] | i ∈{0, 1, . . . ,n}}.

(d) Some chessboard of G looks like the chessboard in Figure 6.

Example 3.3. The sequence (3, 3, 2, 2, 1, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0) is the labelling sequence of the fan

graph F8 whose representations by the graph chessboard and the labelling table are seen in Figure 6.


320 M. Haviar & S. Kurtuĺık CUBO
23, 2 (2021)

4 Double and triple fan graphs and their descriptions

By a double fan graph DFn we will mean the fan graph Fn with extra n pendant vertices, which

are attached to the main path Pn. Hence double fan graphs DFn can be understood such that we

connect n paths P2 to a given fan graph Fn by identifying one vertex of each of the paths P2 with

one vertex of the main path Pn of the fan graph. When we connect this way n paths P3 to a fan

graph Fn, we get a triple fan graph TFn.

In Figure 7 we see the double fan graph DF5 on the left side and the triple fan graph TF4 on the

right side.

Figure 7: The double fan graph DF5 (left) and the triple fan graph TF4 (right)

We can divide vertices of such graphs into these groups: (i) the root vertex, which forms together

with n adjacent edges the “bottom” star, (ii) the “middle” vertices of the main path Pn, and

(iii) the “upper” pendant vertices, which together with the “middle” vertices form n paths P2

resp. P3 connected to the main path. Hence double fan graphs DFn resp. triple fan graphs TFn

can be understood as certain extensions of the fan graphs by adding in the “upper part” n paths

P2 (in double fan graphs) resp. n paths P3 (in triple fan graphs). We will often refer to the

“bottom”, “middle” and “upper parts” (in spite of the fact these parts are not pairwise disjoint

and our naming of these parts refers only to our chosen visualization of these graphs) to assist in

our proofs.

Example 4.1. The sequence (2, 1, 1, 0, 0, 1, 2, 3, 4, 4, 3, 2, 1, 0) is a labelling sequence of a gracefully

labelled double fan graph DF5 of size 14 and order 11. The corresponding graph chessboard and

labelling table are in Figure 8. Because the dots in the graph chessboard representing the edges of

the mentioned “bottom”, “middle” and “upper parts” of the double fan graph look respectively like

the “bottom part”, the “head” and the “neck” of a swan, we will refer to such chessboards as swan

chessboards.

In the next theorems we characterise double fan graphs DFn and triple fan graphs TFn by their

simple chessboards, labelling sequences and labelling relations. Within these characterisations we

prove there are specific graceful labellings of these graphs, thus we show the graphs DFn and TFn


CUBO
23, 2 (2021)

A new class of graceful graphs: k-enriched fan graphs 321

0 4 1 3

5 13 7 11

2

9

14

1 2 3 4 5 6 7 8 9 10 11 12 13 14

2 1 1 0 0 1 2 3 4 4 3 2 1 0
3 3 4 4 5 7 9 11 13 14 14 14 14 14

Figure 8: Representations of the gracefully labelled double fan graph DF5

are graceful. So our double and triple fan graphs are new additions to the list of graceful graphs.

Theorem 4.2. Let G be a graph of size m = 3n− 1 for some n ∈ N −{1}. Then the following
are equivalent:

(1) G is the double fan graph DFn.

(2) There is a graceful labelling of G with a swan chessboard.

(3) There exists a labelling sequence L = (j1,j2, ...,jm) of G such that

ji =



⌊
n−i

2

⌋
, if i < n,

i−n, if n ≤ i < 2n,

m− i, if i ≥ 2n.

(LSDFG)

(4) There exists a labelling sequence L of G with the labelling relation

A(L) ={[u,v] | u,v ∈{0, 1, . . . ,n− 1}, u < v, n− 1 ≤ u + v ≤ n}∪

{[u,n + 2u] | u ∈{0, 1, . . . ,n− 1}}∪

{[n− 1 −u,m] | u ∈{0, 1, . . . ,n− 1}}.

Proof. (1) ⇒ (2) Let G be the double fan graph DFn. We will label it in the following way. Let
the labelling of the single vertex at the “bottom” (the root of DFn) be m. Let the vertices of the

middle path Pn be labelled from one end-vertex of Pn gradually by numbers 0,n−1, 1,n−2, 2, ...


322 M. Haviar & S. Kurtuĺık CUBO
23, 2 (2021)

(see Figure 8). Hence the second end-vertex is labelled by
⌊
n
2

⌋
. Finally we will label n pendant

vertices in the “upper part”. We start from the vertex which is attached to end-vertex, at which

we started the labelling of the main path Pn. We label the vertices from this vertex gradually by

numbers n,m−1,n + 2,m−3,n + 4, .... We get edges with labellings {0,n},{n−1,m−1},{1,n +
2},{n − 2,m − 3}, and so on, in this “upper part”. Now our labelling is done and we show this
labelling is graceful with a corresponding swan chessboard (see Figure 8). One can easily verify

the following statements:

(i) The “bottom part” of G which is the star of size n is in the chessboard represented by n

dots in the bottom row with coordinates [m, 0], [m, 1], ..., [m,n− 1] which form the “bottom
of the swan”.

(ii) The “middle part” of G which is the path Pn is in the chessboard represented by n− 1 dots
with coordinates [n−1, 0], [n−1, 1], [n−2, 1], [n−2, 2], ... which form the “head of the swan”.

(iii) The “upper part” of G which is the union of n paths P2 is in the chessboard represented by

n dots with coordinates [n, 0], [n + 2, 1], [n + 4, 2], [n + 6, 3], ... which form the “neck of the

swan”.

The described swan chessboard with three blocks of dots obviously has one dot on each diagonal.

Hence G is graceful.

(2) ⇒ (3) Assume we have a graceful labelling of G with a swan chessboard (as in Figure 8). We
will verify that when we make the labelling sequence corresponding to this graceful labelling, we

get exactly the labelling sequence satisfying (LSDFG). We use the distribution of dots in a swan

chessboard into three blocks as in the previous part of the proof. So we consider the “head”, the

“neck” and the “bottom part” of a “swan”. One can verify that these three blocks of dots in our

chessboard can be assigned to the corresponding integers in the labelling sequence. The first block

of dots, the “head”, is represented in the corresponding labelling sequence by the integers ji of the

form
⌊
n−i

2

⌋
for i < n. The second block of dots, the “neck”, is represented in the corresponding

labelling sequence by the integers ji of the form i − n for n ≤ i < 2n. The third block of dots,
the “bottom part”, is represented in the corresponding labelling sequence by the integers ji of the

form m− i for i ≥ 2n.

We have shown that there exists a labelling sequence of G satisfying the formula (LSDFG).

(3) ⇒ (4) Assume we have a labelling sequence L of G which satisfies (LSDFG). We will show that
the labelling relation A(L) from this labelling sequence consists of the pairs as described in (4).

Indeed, one can verify that the non-negative integers ji from the labelling sequence, which have the

form
⌊
n−i

2

⌋
for i < n, correspond in A(L) to the pairs [u,v] where u,v ∈ {0, 1, . . . ,n− 1}, u < v

and n − 1 ≤ u + v ≤ n. The next ji from the labelling sequence, which have the form i − n for


CUBO
23, 2 (2021)

A new class of graceful graphs: k-enriched fan graphs 323

n ≤ i < 2n, correspond to the pairs [u,n + 2u] for u ∈ {0, 1, . . . ,n − 1}. Finally, ji from the
labelling sequence, which have the form m− i for i ≥ 2n, correspond to the pairs [n− 1 −u,m]
for u ∈{0, 1, . . . ,n− 1}.

(4) ⇒ (1) Assume that there exists a labelling sequence L of G with the labelling relation A(L)
as in (4). From the definition we know the labelled edges of G correspond to the pairs in A(L).

One can verify that the pairs [n − 1 − u,m] from A(L) for u ∈ {0, 1, . . . ,n − 1} correspond to
the edges in “the bottom part” of graph G which therefore is a star of size n. The pairs [u,v]

from A(L) for u,v ∈ {0, 1, . . . ,n − 1}, u < v and such that n − 1 ≤ u + v ≤ n correspond to
the edges in “the middle part” of G which therefore is the path Pn. Finally, the pairs [u,n + 2u]

for u ∈{0, 1, . . . ,n− 1} correspond to the edges in “the upper part” of G which therefore form n
paths P2 connected to the main path Pn. So the three parts in A(L) correspond to the three parts

of the double fan graph DFn.

Hence a double fan graph can always be gracefully labelled so that its chessboard has the “head”,

the “neck” and the “bottom part” of a “swan”. In the rest of this section we focus on a description

of triple fan graphs.

Example 4.3. The sequence (2, 2, 1, 1, 0, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4, 5, 5, 4, 3, 2, 1, 0) is a labelling

sequence of a triple fan graph of size 23 and order 19. The corresponding graph diagram, graph

chessboard and labelling table are in Figure 9.

Notice that while the swan chessboard of a double fan graph had one “neck” connecting the “head”

and the “bottom part” of the “swan”, the simple chessboard of a triple fan graph has 3 blocks of

dots that look like a “swan without head”, then “the head separated from the neck”, and one extra

“separated neck”. Hence we will refer to such simple chessboards representing the triple fan graphs

as 3-part swan chessboards.

The following characterisations of triple fan graphs can be proven using a method similar to that

used in the previous theorem, and will be covered by the general case in the subsequent section.


324 M. Haviar & S. Kurtuĺık CUBO
23, 2 (2021)

0 5 1 4 2 3

12 22 14 20 16 18

6 11 7 10 8 9

23

1 2 3 4 5 6 7 8 9 10 11

2 2 1 1 0 6 7 8 9 10 11
3 4 4 5 5 12 14 16 18 20 22

12 13 14 15 16 17 18 19 20 21 22 23

0 1 2 3 4 5 5 4 3 2 1 0
12 14 16 18 20 22 23 23 23 23 23 23

Figure 9: Representations of the gracefully labelled triple fan graph TF6

Theorem 4.4. Let G be a graph of size m = 4n− 1 for some n ∈ N −{1}. Then the following
are equivalent:

(1) G is the triple fan graph TFn.

(2) There is a graceful labelling of G with a 3-part swan chessboard.


CUBO
23, 2 (2021)

A new class of graceful graphs: k-enriched fan graphs 325

(3) There exists a labelling sequence L = (j1,j2, ...,jm) of G such that

ji =




⌊
n−i

2

⌋
, if i < n,

i, if n ≤ i < 2n,

i− 2n, if 2n ≤ i < 3n,

m− i, if i ≥ 3n.

(LSTFG)

(4) There exists a labelling sequence L of G with the labelling relation

A(L) ={[u,v] | u,v ∈{0, 1, . . . ,n− 1}, u < v, n− 1 ≤ u + v ≤ n}∪

{[u, 2u] | u ∈{n,n + 1, . . . , 2n− 1}}∪

{[u, 2n + 2u] | u ∈{0, 1, . . . ,n− 1}}∪

{[n− 1 −u,m] | u ∈{0, 1, . . . ,n− 1}}.

5 General case: k-enriched fan graphs kFn and their

descriptions

According to the previous section we would assume that the more “separated necks” we have in

the graph chessboard, the longer the paths in the “upper part” of the graph will be. Our work with

Graph processor introduced in [7] and much used also in [5] has led us to a surprising observation

that the “necks” in the graph chessboard do not represent in the corresponding graph the paths

but the stars. We use for these graphs the term k-enriched fan graphs kFn, where k represents

the order of the stars Sk in the “upper part” of the graph and n represents the order of the “middle”

path Pn. Now we formally define this new term.

Definition 5.1. The k-enriched fan graph kFn, for fixed integers k,n ≥ 2, is the graph of size
(k + 1)n − 1 obtained by connecting n copies of the star Sk of order k to the fan graph Fn such
that one vertex of each copy of the star Sk is identified with one vertex of the main path Pn of Fn.

We notice that here the stars Sk are connected to the main path Pn of the fan graph Fn exactly as

in the previous section the paths P2 (which are the stars S2) resp. P3 (the stars S3) were connected

to the main path Pn of Fn in the case of the double fan graphs DFn resp. triple fan graphs TFn.

Example 5.2. In Figure 10 we see a gracefully labelled 4-enriched fan graph 4F6 obtained by

connecting 6 copies of stars S4 of order 4 to the fan graph F6 as described above. The corresponding

simple chessboard and labelling table are also in Figure 10. The labelling sequence of this graph is

(2, 2, 1, 1, 0, 12, 13, 14, 15, 16, 17, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4, 5, 5, 4, 3, 2, 1, 0).


326 M. Haviar & S. Kurtuĺık CUBO
23, 2 (2021)

We notice that we can divide the vertices of the k-enriched fan graph kFn with any k ≥ 2 similarly
as in the case of double and triple fan graphs. Hence the graph consists of the “bottom part” (the

root vertex and the adjacent edges), the “middle part” (the main path Pn) and the “upper part”

(the disjoint union of n stars Sk). The corresponding simple chessboard of the k-enriched fan graph

kFn for k ≥ 3 has k blocks of dots that form a “swan without head”, then “the separated head”,
and k−2 extra “separated necks”. Hence we will refer to such simple chessboards representing the
k-enriched fan graphs kFn as k-part swan chessboards.

Theorem 5.3. Let G be a graph of size m = (k + 1)n− 1 for some fixed integers k,n ≥ 2. Then
the following are equivalent:

(1) G is the k-enriched fan graph kFn.

(2) There is a graceful labelling of G with a k-part swan chessboard.

(3) There exists a labelling sequence L = (j1,j2, ...,jm) of G such that

ji =




⌊
n−i

2

⌋
, if i < n,

i−n + (k − 2)n, if n ≤ i < 2n,

i−n + (k − 4)n, if 2n ≤ i < 3n,
...

...

i−n + (k − 2(k − 1))n, if (k − 1)n ≤ i < kn,

m− i, if i ≥ kn.

(LSKFG)

(4) There exists a labelling sequence L of G with the labelling relation A(L) of the form

{[
⌊
n−i

2

⌋
,
⌊
n−i

2

⌋
+ i] | i < n}∪

{[i−n + (k − 2)n, 2i−n + (k − 2)n] | n ≤ i < 2n}∪

{[i−n + (k − 4)n, 2i−n + (k − 4)n] | 2n ≤ i < 3n}∪
...

{[i−n + (k − 2(k − 1))n, 2i−n + (k − 2(k − 1))n] | (k − 1)n ≤ i < kn}∪

{[m− i,m] | i ≥ kn}.

Proof. (1) ⇒ (2) Let G be the k-enriched fan graph kFn. We will label the graph G in a way
similar to those labellings for the double and triple fan graphs. Let the labelling of the root of kFn

be m. Let the vertices of the main path Pn be labelled from one end-vertex of Pn (we see it in

Figure 10 from the left side) gradually by numbers 0,n−1, 1,n−2, ... Hence the second end-vertex


CUBO
23, 2 (2021)

A new class of graceful graphs: k-enriched fan graphs 327

0 5 1 4 2 3

18 28 20 26 22 24

12 6 17 11 13 7 16 10 14 8 15 9

29

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

2 2 1 1 0 12 13 14 15 16 17 6 7 8 9
3 4 4 5 5 18 20 22 24 26 28 18 20 22 24

16 17 18 19 20 21 22 23 24 25 26 27 28 29

10 11 0 1 2 3 4 5 5 4 3 2 1 0
26 28 18 20 22 24 26 28 29 29 29 29 29 29

Figure 10: Representations of the gracefully labelled 4-enriched fan graph 4F6

of Pn is labelled by
⌊
n
2

⌋
. We start to label the central vertices of the n stars Sk in the “upper

part” of the graph G from the central vertex of Sk attached to the vertex of the main path Pn

labelled by n − 1. We label this vertex by m − 1, the next central vertex of Sk attached to the
vertex n−2 will be labelled by m−3, the central vertex of Sk attached to the vertex n−3 will be
labelled by m− 5 and so on, we end by labelling the central vertex of Sk attached to the vertex 0


328 M. Haviar & S. Kurtuĺık CUBO
23, 2 (2021)

by m−2n + 1 (see Figure 10). To label the remaining vertices of the n stars Sk, we begin with the
star, whose central vertex is labelled by m− 1. The remaining vertices of this star are labelled by
((m− 1) − (2n− 1)), ((m− 1) − (3n− 1)),... It does not matter in what ‘direction’ we label these
vertices. We proceed in the same way with labelling the remaining vertices of the other stars in

the “upper part” of G, the role of the previous number m− 1 is always played by the labelling of
the central vertex of the given star (see Figure 10). Now our labelling of G is done and we show

that this labelling is graceful with a k-part swan chessboard.

For this we use a visualization via the corresponding simple chessboard of G (see Figure 10). One

can easily verify that:

(i) The “bottom part” of G which is the star of size n is in the simple chessboard represented

by n dots with coordinates [m, 0], [m, 1], ..., [m,n− 1] in the bottom row of the chessboard.
(Exactly as for the double and triple fan graphs.)

(ii) The “middle part” of G which is the main path Pn is in the chessboard represented by n−1
dots with coordinates [n−1, 0], [n−1, 1], [n−2, 1], [n−2, 2], ... which form a certain “separated
head” in the case k ≥ 3. (Exactly as for the triple fan graphs.)

(iii) The “upper part” of G which is the union of n stars Sk is in the simple chessboard represented

by k − 1 “necks” each consisting of n dots.

Hence the graph chessboard corresponding to our labelling is a k-part swan chessboard (as chess-

board in Figure 10) and obviously it has exactly one dot on each diagonal. So the described

labelling of G is graceful.

(2) ⇒ (3) Assume we have a graceful labelling of G with a k-part swan chessboard. Consider
the following k blocks of dots of this chessboard: the “separated head”, k − 1 swan “necks” and
the bottom row of the chessboard. One can verify that the “separated head” is represented in

the corresponding labelling sequence by the integers ji having the form
⌊
n−i

2

⌋
for i < n. The

first “neck” from the right below the main diagonal is represented in the corresponding labelling

sequence by the integers ji having the form i−n + (k − 2)n for n ≤ i < 2n. The second “neck”
from the right below the main diagonal is represented in the corresponding labelling sequence by

the integers ji having the form i−n + (k−4)n for 2n ≤ i < 3n, and so on. Finally, the last “neck”
(the first one from the left) is represented in the corresponding labelling sequence by the integers

ji having the form i−n+ (k−2(k−1))n for (k−1)n ≤ i < kn. The bottom row of the chessboard
is represented in the corresponding labelling sequence by the integers ji having the form m− i for
i ≥ kn.

So we have shown that the labelling sequence corresponding to our k-part swan chessboard satisfies

the formula (LSKFG).


CUBO
23, 2 (2021)

A new class of graceful graphs: k-enriched fan graphs 329

(3) ⇒ (4) Assume there is a labelling sequence L of G which satisfies (LSKFG). One can verify that
the corresponding labelling relation A(L) consists of the pairs as described in (4). Indeed, the non-

negative integers ji from the labelling sequence having the form
⌊
n−i

2

⌋
for i < n correspond in A(L)

to the pairs [
⌊
n−i

2

⌋
,
⌊
n−i

2

⌋
+ i]. The next integers ji from the labelling sequence, which have the

form i−n+ (k−2)n for n ≤ i < 2n, correspond in A(L) to pairs [i−n+ (k−2)n, 2i−n+ (k−2)n].
Further, the integers ji from the labelling sequence, which have the form i − n + (k − 4)n for
2n ≤ i < 3n, correspond in A(L) to pairs [i−n + (k − 4)n, 2i−n + (k − 4)n], and so on for the
next parts of the labelling sequence, which correspond to the “necks”. Finally, the integers ji from

the labelling sequence, which have the form m− i for i ≥ kn, correspond to the pairs [m− i,m].

(4) ⇒ (1) Let L be a labelling sequence of G with the labelling relation A(L) as in (4). The pairs
[m− i,m] in A(L) for i ≥ kn correspond to the edges of the “bottom part” of G, which therefore
is a star of order n. The pairs [

⌊
n−i

2

⌋
,
⌊
n−i

2

⌋
+ i] in A(L) for i < n correspond in the graph G to

the edges which form the “middle path” Pn. The remaining pairs in A(L) correspond to the edges

in “the upper part” of G. More precisely, each of the pairs [i − n + (k − 2)n, 2i − n + (k − 2)n]
for n ≤ i < 2n corresponds to one edge in each of the n “upper” stars Sk, each of the pairs
[i − n + (k − 4)n, 2i − n + (k − 4)n] for 2n ≤ i < 3n corresponds to one of the (other) edges
in each of the n stars Sk in the “upper part” of G, and so on, and finally, each of the pairs

[i−n+ (k−2(k−1))n, 2i−n+ (k−2(k−1))n] for (k−1)n ≤ i < kn corresponds to the remaining
edges in each of the n stars Sk in the “upper part” of G. So we get n stars Sk in the “upper part”

of G. Thus we have in G the “bottom” star of size n, the “middle” path Pn and the n “upper”

stars Sk connected to the vertices of the “middle” path Pn. Hence the graph G is the k-enriched

fan graph kFn.

6 Conclusion

Studies of other extended fan graphs can be found in the literature. Some of them are seen in

Figure 11 below. The first two graphs are taken from [1]. The author named the first one as a

double fan graph, but it is different from our double fan graph as defined in this paper. It consists

of two fan graphs that have a common main path. The second graph was obtained by adding some

edges to a vertex of the main path.

One of the possibilities for other extensions of fan graphs would be adding paths of the same length

Pk (not stars Sk as in our case) to the main path Pn of the fan graph Fn. These graphs and our

k-enriched fan graphs kFn would be the same for the cases k = 2 and k = 3. Such extended fan

graphs, let us denote them as PkFn (our k-enriched fan graphs kFn in this more universal notation

would be denoted SkFn) can look like the third graph in Figure 11. This graph would be the

extended fan graph P4F3 as the paths P4 are connected to the main path of the fan graph F3. We


330 M. Haviar & S. Kurtuĺık CUBO
23, 2 (2021)

conclude our paper with the following open problem:

Problem 6.1. Are the extended fan graphs PkFn (obtained by connecting in the described way n

paths Pk to the main path Pn of the fan graph Fn) graceful? And if so, is there a characterization

of them via a certain “canonical” graph chessboard and the corresponding labelling sequence and

the labelling relation like the characterizations of the graceful graphs presented in this paper?

Figure 11: Other extended fan graphs

Acknowledgements

The first author acknowledges a support by Slovak VEGA grant 2/0078/20 and a Visiting Profes-

sorship at University of Johannesburg. Both authors acknowledge assisting remarks by Dr. Andrew

P.K. Craig from the University of Johannesburg. The authors also thank the anonymous referee

for pointing to a recent paper [12] where (generalized) comb-like trees are introduced which can be

considered as new candidates for families of graceful graphs and then possibly also characterized

in the manner presented in this paper.


CUBO
23, 2 (2021)

A new class of graceful graphs: k-enriched fan graphs 331

References

[1] S. Amutha and M. Uma Devi, “Super Graceful Labeling for Some Families of Fan Graphs”,

Journal of Computer and Mathematical Sciences, vol. 10, no. 8, pp. 1551–1562, 2019.

[2] J. A. Gallian, “A Dynamic Survey of Graph Labeling”, Electron. J. Combin., # DS6, Twenty-

second edition, 2019.

[3] M. Gardner, “Mathematical Games: The graceful graphs of Solomon Golomb”, Sci. Am., vol.

226, no. 23, pp. 108–112, 1972.

[4] S. W. Golomb, “How to number a graph”, In: Graph Theory and Computing, pp. 23–37,

Academic Press, 1972.

[5] M. Haviar and M. Ivaška, Vertex Labellings of Simple Graphs. Research and Exposition in

Mathematics, vol. 34, Lemgo, Germany: Heldermann-Verlag, 2015.

[6] P. Hrnčiar and A. Haviar, “All trees of diameter five are graceful”, Discrete Math., vol. 233,

no. 1-3, pp. 133–150, 2001.

[7] M. Ivaška, “Chessboard Representations and Computer Programs for Graceful Labelings of

Trees”, Student Competition ŠVOČ, M. Bel University, Banská Bystrica, 2009.

[8] S. Kurtuĺık, “Graceful labellings of graphs”, MSc. thesis, 52 pp., Department of Mathematics,

M. Bel University, Banská Bystrica, 2020.

[9] A. Rosa, “O cyklických rozkladoch kompletného grafu” [On cyclic decompositions of the

complete graph], PhD thesis (in Slovak), Československá akadémia vied, Bratislava, 1965.

[10] A. Rosa, “On certain valuations of the vertices of a graph”, In: Theory of Graphs (Internat.

Symposium, Rome, July 1966), pp. 349–355, New York: Gordon and Breach, 1967.

[11] D. A. Sheppard, “The factorial representation of major balanced labelled graphs”, Discrete

Math., vol. 15, no. 4, pp. 379–388, 1976.

[12] K. Xu, X. Li and S. Klavžar, “On graphs with largest possible game domination number”,

Discrete Math., vol. 341, no. 6, pp. 1768–1777, 2018.


	Introduction
	Preliminaries
	Fan graphs and their descriptions
	Double and triple fan graphs and their descriptions
	General case: k-enriched fan graphs kFn and their descriptions
	Conclusion