关于图的 L(2 ,1)标号核图(英文)

ON THE L(2,1)-LABELING CORE GRAPH OF GRAPHS

图的 L(2 ,1 )标号核图来自频率分配问题而导致的图论问题 .在本文中 ,我们证得 :(i)对任意简单图G,存在 G的一个标号核图 Gcore,使得 L(G) =L(Gcore)和 L(G)≥ |V(Gcore) |- 1 ;(ii)设图 G有 p个顶点且边集|E(G) |≠ ,存在路 Pi G(1≤ i≤ m)和路 Hs Gc(1≤ s≤ n) ,其中在 G中 V(Pi)∩ V(Pj) = (i≠ j) ,在 Gc中 V(Ps)∩ V(Pt) = (s≠ t) ,则有 mt=1|V(Pt) |+ ns=1|V(Hs) |- (m +n)≥ p;(iii) G是 p(p≥ 5)个顶点的简单图 ,则有 p +3≤ L(G) +L(Gc)≤ 3p -

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 any simple graph G, there exits a L(2,1)-labeling core graph G core of G such that L(G)=L(G core) and L(G)≥ |V(G core)|-1.(ii) Let G be not complete graph with p vertices and |E(G)|≠,there are paths P iG(1≤i≤m) and paths H sGc(1≤s≤n) where V(P i)∩V(P j)=(i≠j) in G and V(P s)∩V(P t)=(s≠t) in Gc, such that mi=1|V(P i)|+ns=1|V(H S)|-(m+n)≥p.(iii) For any simple graph G with p vertices (p≥5), then p+3≤L(G)+L(GC)≤3p-4.