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

摘要

图的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 G(1≤s≤n),其中在G中V(Pi)∩V(Pj)=φ(i≠j),在G中V(P,)∩V(Pt)=φ(s≠t),则有m∑t=1|V(Pt)|+n∑s=1|V(Hs)|-(m+n)≥p;(iii)G是p(p≥5)个顶点的简单图,则有p+3≤L(G)+L(G)≤3p-4.%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.