$\mathrm{\Delta }$-Optimum Forbidden Subgraphs and Exclusive Sum Labellings of Graphs

Abstract

The notions of sum labelling and sum number of graphs were introduced by F. Harary [1] in 1990. A mapping $f$ is called a sum labelling of a graph $G(V,E)$ if it is an injection from $V$ to a set of positive integers such that $uv\in E$ if and only if there exists a vertex $w\in V$ such that $f(w)=f(x)+f(y)$. In this case, $w$ is called a working vertex. If $f$ is a sum labelling of $G$ with $r$ isolated vertices, for some nonnegative integer $r$, and $G$ contains no working vertex, $f$ is defined as an exclusive sum labelling of the graph $G$ by M. Miller et al. in paper [2]. The least possible number $r$ of such isolated vertices is called the exclusive sum number of $G$, denoted by $ϵ(G)$. If $ϵ(G)=\mathrm{\Delta }(G)$, the labelling is called $\mathrm{\Delta }$-optimum exclusive sum labelling and the graph is said to be $\mathrm{\Delta }$-optimum summable, where $\mathrm{\Delta }=\mathrm{\Delta }(G)$ denotes the maximum degree of vertices in $G$. By using the notion of $\mathrm{\Delta }$-optimum forbidden subgraph of a graph, the exclusive sum numbers of crown $C_n\odot K_1$ and $(C_n\odot K_1)$ are given in this paper. Some $\mathrm{\Delta }$-optimum forbidden subgraphs of trees are studied, and we prove that for any integer $\mathrm{\Delta }\ge 3$, there exist trees not $\mathrm{\Delta }$-optimum summable. A nontrivial upper bound of the exclusive sum numbers of trees is also given in this paper.