Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651464 | Discrete Mathematics | 2006 | 12 Pages |
Let GG be a graph with vertex set V(G)V(G) and edge set E(G)E(G). A labeling f:V(G)→{0,1}f:V(G)→{0,1} induces an edge labeling f*:E(G)→{0,1}f*:E(G)→{0,1}, defined by f*(xy)=|f(x)-f(y)|f*(xy)=|f(x)-f(y)| for each edge xy∈E(G)xy∈E(G). For i∈{0,1}i∈{0,1}, let ni(f)=|{v∈V(G):f(v)=i}|ni(f)=|{v∈V(G):f(v)=i}| and mi(f)=|{e∈E(G):f*(e)=i}|mi(f)=|{e∈E(G):f*(e)=i}|. Let c(f)=|m0(f)-m1(f)|c(f)=|m0(f)-m1(f)|. A labeling ff of a graph GG is called friendly if |n0(f)-n1(f)|⩽1|n0(f)-n1(f)|⩽1. A cordial labeling of GG is a friendly labeling ff for which c(f)⩽1c(f)⩽1. A graph GG is a uniformly cordial graph if every friendly labeling of GG is cordial. It is shown that a connected graph GG of order n⩾2n⩾2 is uniformly cordial if and only if n=3n=3 and G=K3G=K3, or nn is even and G=K1,n-1G=K1,n-1.