摘要
Abstract
The L (2,1)-labeling core graph of a graph G is from the L (2,1)-labeling problem and the L (2,1)labeling problem of graph G is from the frequency assignment problem. In this paper, we have: (i) For anysimple graph G, there exits a L(2,1)-labeling core graph Gcore of G such that L(G) =L(Gcore) and L(G)≥| V(Gcore) |- 1. (ii) Let G be not complete graph with p vertices and | E(G)|φ, there are paths Pi G(1≤i ≤m) and paths Hi Gc(1≤s≤n) where V(Pi) ∩V(Pj) =φ(i≠j) in G and V(Ps) ∩V(Pt)=φ(s≠t) inGc, such that m∑i=1 |V(Pi) | + n∑s=1 |V(Hs)| - (m + n) ≥p. (iii) For any simple graph G with p vertices (p≥5), then p+3≤L(G)+L(Gc)≤3p-4.关键词
L(2,1)标号函数,补图,L(2,1)标号核图Key words
L(2,1)-labeling function, complementary graph, L(2,1)-labeling core graph
