Δ-Optimum Forbidden Subgraphs and Exclusive Sum Labellings of Graphs

被引:0
作者
Wei, Jianxin [1 ,2 ]
Fan, Baoqiang [2 ]
机构
[1] Lanzhou Univ, Sch Math & Stat, Lanzhou 730000, Peoples R China
[2] Ludong Univ, Sch Math & Informat, Yantai 264025, Peoples R China
关键词
NUMBER;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 is an element of E if and only if there exists a vertex w is an element of 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 boolean OR rK(1) for some nonnegative integer r and G contains no working vertex, f is defined as an exclusive sum labelling of the graph C 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 epsilon(G). If epsilon(G) = Delta(G), the labelling is called Delta-optimum exclusive sum labelling and the graph is said to be is Delta-optimum summable, where Delta = Delta(G) denotes the maximum degree of vertices in G. By using the notion of Delta-optimum forbidden subgraph of graph the exclusive sum numbers of crown C-n circle dot K-1 and (C-n circle dot K-1) are given in this paper. Some Delta-optimum forbidden subgraphs of trees are studied and we prove that for any integer Delta >= 3 there exist trees not Delta-optimum summable, and a nontrivial upper bound of the exclusive sum numbers of trees is also given in this paper.
引用
收藏
页码:387 / 402
页数:16
相关论文
共 15 条
  • [1] [Anonymous], 1989, B MALAYS MATH SCI SO
  • [2] Dou WQ, 2007, ARS COMBINATORIA, V82, P3
  • [3] ELLINGHAM MN, 1993, ARS COMBINATORIA, V35, P335
  • [4] Harary F., 1990, Congr. Numer., V72, P101
  • [5] Harary F., 1969, Graph Theory
  • [6] Hartsfield, 1995, DISCRETE MATH, V141, P163
  • [7] Miller M., 2005, Journal of Combinatorial Mathematics and Combinatorial Computing, V55, P137
  • [8] Miller M., 1998, B I COMBIN APPL, V22, P79
  • [9] Bounds on the number of isolates in sum graph labeling
    Nagamochi, H
    Miller, M
    Slamin
    [J]. DISCRETE MATHEMATICS, 2001, 240 (1-3) : 175 - 185
  • [10] Ryan J, 2009, AKCE INT J GRAPHS CO, V6, P113