Jianxin Wei

The notion of sum graph was introduced by F. Harary. The sum graph $G^{+}(S)$ of a finite subset $S$ of the set $N^{*}$ of all positive integers is the graph $(S, E)$ with $uv\in E$ if and only if $u+v\in S$. A graph $G$ is said to be a sum graph if it is isomorphic to the sum graph $G^{+}(S)$ of some $S\subset N^{*}$. In this case, we say that $S$ gives a sum labelling for $G$. The sum number $\sigma(G)$ is the smallest number of isolated vertices which when added to $G$ result in a sum graph. In 1994, F. Harary introduced the concepts of integral sum graph and integral sum number of a graph with $S\subset Z$ (the set of all integers) instead of $S\subset N^{*}$.
In a labelling of a sum graph $G$, vertexes whose label corresponds to an edge of $G$ are said to be working vertices. Graphs that can only be labelled in such a way that all the working vertexes are also isolates are called exclusive.
From a practical point of view, sum graph labelling can be used as a compressed representation of a graph, a data structure for representing the graph, and an alternative method for defining and storing graphs.
Now the research aims at two aspects. One is to study the relation between the (integral) sum number and other parameters and structure of graph. The other is at determining the sum number of some graph classes.
In this thesis we obtain the following theorems.
Theorem 1. Let $n\geq 3$, then $\sigma(C_{n}\odot K_{1})= 1$.
Theorem 2. Let $n\geq 3$, then $\sigma(S(C_{n}\odot K_{1}))=1$.
Theorem 3. Let $n\geq 3$, then $\sigma(C_{n}\odot K_{1})^{*}=1$.
Theorem 4. The sum number of all 2-regular graphs with the exception of $C_{4}$ is 2.
Theorem 5. Let $r\geq 3$, then $\sigma(K_{1, 1, r})= r$.
Theorem 6. Let $k>3, r\geq 2k-3$, then $\sigma(K_{1, \cdots, 1, r})= r+(k-1)$, where $k$ is the number of 1 in $K_{1, \ldots, 1, r}$.
Theorem 7. Let $t\geq r+s-1$, then $r+s\leq\sigma(K_{r, s, t})\leq 2t+r+s-2$.
Theorem 8. $\sigma(D_{n})=2$, $\zeta(D_{n})=0$, where $D_{n}$ is the Dutch $m$-windmill.
Theorem 9. $F_{n}$ is exclusive, where $F_{n}$ is French $m$-windmill.
Theorem 10. Let $S_{1}, S_{2}$ denote the sum labellings of $G\cup\sigma(G)K_{1}, H\cup\sigma(H)K_{1}$ respectively and suppose $\max S_{1}=m, \min S_{2}=n, (m, n)=1$,, if $\min S_{1}/\{n\}\geq 2n$ or $2\max S_{2}/\{m\}\leq m$, then $\sigma(G\cup H)\leq\sigma(G)+\sigma(H)-1$.
Theorem 11. Let $G$ be a connected integral sum graph with $n(\geq3)$ vertices and $m$ edges . If $G$ has only one saturated vertex , then $n-1\leq m\leq\lfloor\frac{3n^{2}-3}{8}\rfloor-1$.
Theorem 12. The smallest order of an integral sum graph with clique number $\omega(G)(\geq3)$ is $2\omega(G)-3$.
Theorem 13. The smallest order of a unit sum graph with clique number $\omega(G)(\geq3)$ is $2\omega(G)-2$.