As known, graph labelling theory has important applications in coding theory, communication networks, logistics and other aspects of science. Some generalized sun-graphs can be regarded as ring-like real-networks. Each node in a network represents a server or client, and every edge joins two nodes if these two nodes are connected in the network. In Operations Research or Systems Engineering Theory and Methods, one very often use graph colorings to divide large systems into subsystems, and one, also, can use graph labellings to distinguish nodes and edges between nodes in order to find some fast algorithms to imitate effective transmission and safe communication in information networks.
On the other hand, Rosa[1] in 1966 proposed a conjecture: Every tree is a graceful tree. There are a lot of results for attacking this conjecture, but it has been known that this conjecture has not been settled down up to now. Lee et al.[2] in 1991 put forward a conjecture: Every tree is a felicitous tree that has the same theoretical value to the graceful tree conjecture and also has the same difficulty to be proved. Both conjectures are NP-hard problems that have attracted many researchers to explore them [3-6]. Attacking mathematical conjecture makes that graph labelling theory rapidly becomes a very active branch in graph theory.
We use standard terminology and notation of graph theory, and graphs mentioned here are finite, simple and undirected. A $(p,q)$-graph has $p$ vertices and $q$ edges. An integer set $\{m, m+1, m+2, \cdots, n\}$ with integers $0\leq m<n$ is denoted as $[m,n]$; similarly, $[k,\ell]^{e}$ denotes an integer set $\{k,k+2,k+4,\cdots,\ell\}$, where $k$ and $\ell$ are even with respect to $0\leq k<\ell$; and $[s,t]^{o}$ stands for an integer set $\{s,s+2,s+4,\cdots,t\}$ with odd integers $s$ and $t$ holding $1\leq s<t$. A leaf is a vertex of degree one.
Definition 1.1 [3] A $(p, q)$-graph $G$ has a proper mapping $f:V(G) \rightarrow [0,q]$, and the edge label $f(uv)$ of each edge $uv \in E(G)$ is defined as $f(uv) =f(u) +f(v)(\bmod q)$. If $f(u)\neq f(v)$ for distinct $u,v \in V(G)$, and the edge label set $\{f(uv): uv \in E(G) \}=[0, q-1]$, then we say both $G$ and $f$ to be felicitous. And write $f(V(G))=\{f(u) : u\in V(G)\}$, $f(E(G))=\{f(uv)=f(u)+f(v) (\bmod q): uv\in E(G)\}$.
Let $C_n=w_1w_2\cdots w_nw_1$ be a cycle of length $n$, where $n\geq 3$. Joining each vertex $w_i(i\in [1,n])$ of $C_n$ with a new vertex $y_i$ out of $C_n$ by an edge obtains a graph, called a sun-graph and denoted as $SC_n$. Furthermore, for integers $r_i\geq 1$ and $k_i\geq 0$ with $i\in [1,n]$, we join each vertex $w_i$ of $C_n$ and the initial vertex $u^i_{j,m_{i,j}}$ of a path $P^i_{j}=u^i_{j,1}u^i_{j,2}\cdots u^i_{j,m_{i,j}}$ for $m_{i,j}\geq 2$, $j\in [1, r_i]$, and join each vertex $w_i$ with $k_i$ new vertices $v_{i,t}$ for $t\in [1,k_i]$ to produce a generalized sun-graph, denoted by GSG$(m_{i,j},r_i,k_i:i\in [1,n])$. It is reasonable to allow some $k_i=0$, that is, no joining the vertex $w_i$ of $C_n$ with new vertex. Clearly, a generalized sun-graph is just a sun-graph when $m_{i,j}=1$, $r_i=1$ and $k_i=0$ for $i\in [1,n]$.
In this article, we focus on finding felicitous labellings of GSG$(m_{i,j},r_i,k_i:i\in [1,n])$ for $r_i=1$ or $2$ and $m_{i,j}=2$ with $i\in [1,n]$ and odd $n$. For the purpose of simplicity, we rewrite GSG$_{n,1,3}={\rm GSG}(m_{i,j}:j\leq r_i,i\in [1,n])$ when $r_i=1$, $m_{i,j}=2$ and $k_i\geq 0$. Thereby, we have
where $u^i_{1}=u^i_{1,1}$ and $u^i_{2}=u^i_{1,2}$. Similarly, ${\rm GSG}_{n,2,3}={\rm GSG}(m_{i,j}:j\leq r_i,i\in [1,n])$ when $r_i=2$, $m_{i,j}=2$ and $k_i\geq 0$, and furthermore
Theorem 2.1 For odd $n\geq 3$, every generalized sun-graph GSG$_{n,1,3}$ admits a felicitous labelling.
Proof Apply the notation in (1.1) for $GSG_{n,1,3}$. Clearly,
where $M=3n+\sum\limits^n_{i=1}k_{i}$ (it may be some $k_i=0$). Let $R=\frac{3n+3}{2}+\sum\limits_{s\in [1,n]^{e}}k_{s}$. We define a labelling $f$ of GSG$_{n,1,3}$ as follows.
(1) $f(u^1_{1})=0$, $f(u^i_{1})=\sum\limits_{s\in [1,i]^{e}}(k_{s}+3)$, $i \in [3,n]^{o}$;
(2) $f(w_{1})=1$, $f(w_{i})=1 +\sum\limits_{s\in [1,i]^{e}}(k_{s}+3)$, $i \in [3,n]^{o}$;
(3) if $k_2\neq 0$, $f(v_{2,m})=m+1$, $m \in[1,k_{2}]$; for $k_j\neq 0$, $f(v_{j,m})=1+m+\sum\limits_{s\in [1,j-2]^{e}}(k_{s}+3)$, $j \in [3,n]^{e}$, $m \in[1,k_{j}]$;
(4) $f(u^2_{2})=k_{2}+2$, $f(u^j_{2})=-1+\sum\limits_{s\in [1,j]^{e}}(k_{s}+3)$, $j \in [3,n]^{e}$;
(5) $f(u^1_{2})=R$, $f(u^i_{2})=R+\sum\limits_{t\in [1,i-2]^{o}}(k_{t}+3)$, $i \in [3,n]^{o}$;
(6) if $k_1\neq 0$, $f(v_{1,m})=R+m$, $m \in[1,k_{1}]$; for $k_i\neq 0$, $f(v_{i,m})=R+\sum\limits_{t\in [1,i-2]^{o}}(k_{t}+3)+m$, $i \in [3,n]^{o}$, $m \in[1,k_{i}]$;
(7) $f(w_{2})=R+k_{1}+1$, $f(w_{j})=R +\sum\limits_{t\in [1,j-3]^{o}}(k_{t}+3)+k_{j-1}+1$, $j \in [3,n]^{e}$;
(8) $f(u^2_{1})=R+k_{1}+2$, $f(u^j_{1})=R +\sum\limits_{t\in [1,j-3]^{o}}(k_{t}+3)+k_{j-1}+2$, $j \in [3,n]^{e}$.
We calculate $f(V({\rm {GSG}}_{n,1,3}))$. Since
and
for $i \in [1,n]^{o}$ and $j \in [1,n]^{e}$. Therefore,
Next, we compute $f(E({\rm {GSG}}_{n,1,3}))$ in the following way:
(1) $f(w_{1})+f(w_{n})=\frac{3n+1}{2}+\sum\limits_{s\in [1,n-1]^{e}}k_{s}=R-1$;
(2) for $i \in [1,n]^{o}$, we have
(3) for $i \in [1,n]^{o}$, thus
(4) for $i \in [1,n]^{o}$, then
(5) when $i \in [1,n]^{o}$ and $j \in [1,n]^{e}$, we have
(6) as $j \in [1,n]^{e}$, we get
(7) for $j \in [1,n]^{e}$,
(8) when $j \in [1,n]^{e}$, we get
We, finally, obtain
So
By Definition 1.1, the generalized sun-graph ${\rm {GSG}}_{n,1,3}$ is felicitous.
Theorem 2.2 For odd $n\geq 3$, every generalized sun-graph GSG$_{n,2,3}$ admits felicitous labellings.
Proof Use the notation shown in (1.2). Clearly, $|V({\rm GSG}_{n,2,3})|=|E({\rm GSG}_{n,2,3})|=M$, where $M=5n+\sum\limits^n_{i=1}k_{i}$ (it may be some $k_i=0$). Let $R=\sum\limits_{s\in [1,n]^{e}}(k_{s}+5)+3$. We define a labelling $f$ of the generalized sun-graph GSG$_{n,2,3}$ by setting
(1) $f(u^1_{1,1})=0$, $f(u^i_{1,1})=\sum\limits_{s\in [1,i]^{e}}(k_{s}+5)$, $i \in [3,n]^{o}$;
(2) $f(w_{1})=1$, $f(w_{i})=1 +\sum\limits_{s\in [1,i]^{e}}(k_{s}+5)$, $i \in [3,n]^{o}$;
(3) $f(u^1_{2,1})=2$, $f(u^i_{2,1})=2+ \sum\limits_{s\in [1,i]^{e}}(k_{s}+5)$, $i \in [3,n]^{o}$;
(4) $f(u^2_{1,2})=3$, $f(u^j_{1,2})=3+ \sum\limits_{s\in [1,j-2]^{e}}(k_{s}+5)$, $j \in [3,n]^{e}$;
(5) if $k_2\neq 0$, $f(v_{2,m})=m+3$, $m \in[1,k_{2}]$; for $k_j\neq 0$, $f(v_{j,m})=3+m+\sum\limits_{s\in [1,j-2]^{e}}(k_{s}+5)$, $j \in [3,n]^{e}$, $m \in[1,k_{j}]$;
(6) $f(u^2_{2,2})=k_{2}+4$, $f(u^j_{2,2})=\sum\limits_{s\in [1,j-2]^{e}}(k_{s}+5)+k_{j}+4$, $j \in [3,n]^{e}$;
(7) $f(u^1_{1,2})=R$, $f(u^i_{1,2})=R+\sum\limits_{t\in [1,i-2]^{o}}(k_{t}+5)$, $i \in [3,n]^{o}$;
(8) if $k_1\neq 0$, $f(v_{1,m})=R+m$, $m \in[1,k_{1}]$; for $k_i\neq 0$, $f(v_{i,m})=R+\sum\limits_{t\in [1,i-2]^{o}}(k_{t}+5)+m$, $i \in [3,n]^{o}$, $m \in[1,k_{i}]$;
(9) $f(u^1_{2,2})=R+k_{1}+1$, $f(u^i_{2,2})=R+\sum\limits_{t\in [1,i-2]^{o}}(k_{t}+5)+k_{i}+1$, $i \in [3,n]^{o}$;
(10) $f(u^2_{1,1})=R+k_{1}+2$, $f(u^j_{1,1})=R+\sum\limits_{t\in [1,j-3]^{o}}(k_{t}+5)+k_{j-1}+2$, $j \in [3,n]^{e}$;
(11) $f(w_{2})=R+k_{1}+3$, $f(w_{j})=R +\sum\limits_{t\in [1,j-3]^{o}}(k_{t}+5)+k_{j-1}+3$, $j \in [3,n]^{e}$;
(12) $f(u^2_{2,1})=R+k_{1}+4$, $f(u^j_{2,1})=R +\sum\limits_{t\in [1,j-3]^{o}}(k_{t}+5)+k_{j-1}+4$, $j \in [3,n]^{e}$.
The subsets of $f(V({\rm {GSG}}_{n,2,3}))$ are: for $i \in [1,n]^{o}$ and $j \in [1,n]^{e}$, we have
Hence,
We come to compute $f(E({\rm {GSG}}_{n,2,3}))$ as follows.
(1) $f(w_{1})+f(w_{n})=2+\sum\limits_{s\in [1,n]^{e}}(k_{s}+5)=R-1$;
(3) for $i \in [1,n]^{o}$,
(4) for $i \in [1,n]^{o}$,
(5) for $i \in [1,n]^{o}$,
(6) for $i \in [1,n]^{o}$,
(7) when $i \in [1,n]^{o}$ and $j \in [1,n]^{e}$,
(8) for $j \in [1,n]^{e}$,
(9) for $j \in [1,n]^{e}$,
(10) $j \in [1,n]^{e}$,
(11) $j \in [1,n]^{e}$,
(12) $j \in [1,n]^{e}$,
Thereby, we get
and furthermore $f(E({\rm {GSG}}_{n,2,3}))=\big [0,\sum\limits^n_{i=1}k_{i}+5n-1\big ]=[0, M-1]$. We claim that ${\rm {GSG}}_{n,2,3}$ is felicitous.
We propose a conjecture: every unicyclic graph is felicitous.