<p>An unsolved problem of graph labeling theory, namely the existence of balanced zero-neighborhood labeling in cubic graphs, is investigated. Particular attention is focused on the class of generalized Petersen graphs <i>GP</i>(<i>n</i>, <i>k</i>). A necessary condition for the existence of balanced zero-neighborhood labeling for <i>GP</i>(<i>n</i>, <i>k</i>) is established. The analysis of its properties has led to results for the graph <i>GP</i>(<i>n</i>,5) that indicate the existence of its structural constraints related to symmetry and the properties of its automorphism group. Structural properties have been obtained for similar graphs, in particular for <i>GP</i>(6<i>m</i>,5), which made it possible to prove that the graph <i>GP</i>(6<i>m</i>,5) does not admit a balanced zero-neighborhood labeling for any m ≥ 3.</p>