Menu
A new graph labeling problem on simple graphs called edge-balanced labeling is introduced by Kong and Lee [11]. They conjectured that all trees except \(K_{1,n}\) where \(n\) is odd, and all connected regular graphs except \(K_2\) are edge-balanced. In this paper, we extend the concept of edge-balanced labeling to multigraphs and completely characterize the edge-balanced multigraphs. Thus, we proved that the above two conjectures are true. A byproduct of this result is a proof that the problem of deciding whether a graph is edge-balanced does not belong to NP-hard.