×

On edge-balanced index sets of some complete \(k\)-partite graphs. (English) Zbl 1211.05149

Summary: Let \(G= (V,E)\) be an undirected graph. A binary labeling \(f: E\to Z_2= \{0,1\}\) is edge-friendly if \(|e_f(0)- e_f(1)|\leq 1\), where \(e_f(i)\) is the number of \(i\)-edges labeled with \(i\), \(i\in Z_2\). Given any edge-friendly labeling \(f\), \(f\) induces a partial vertex labeling \(f^+\) on \(V\) defined by \(f^+(v)= 0,\,1\), or undefined, iff the number of \(0\)-edges incident with \(x\) is greater than, less than, or equal to, the number of \(1\)-edges incident with \(x\). Let \(\Sigma\) be the set of all edge-friendly labelings of \(G\). For \(f\in E\), the edge-balanced index of \(f\) is defined as \(\delta(f)=|v_f(0)- v_f(1)|\), where \(v_f(i)\) is the number of \(i\)-vertices labeled with \(i\), \(i\in Z_2\). The edge-balance index set of \(G\) is defined as \(\text{EBI}(G)= \{\delta(f): f\in\Sigma\}\). If \(0\in \text{EBI}(G)\) or \(1\in\text{EBI}(G)\), then \(G\) is an edge-balanced graph.
In this paper we determine the edge-balance index set of some complete \(k\)-partite graphs.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDFBibTeX XMLCite