On Edge-Balance Index Sets of Generalized Theta Graphs

摘要

Any edge labeling f : E → {0,1} of a simple graph G = (V, E) induces a vertex labeling f~* : V → {0,1} defined by f~*(x) = i if x is incident to more i-edges than (1-i)-edges, and f~*(x) is unlabeled if x is incident to an equal number of 0- and 1-edges. Denote by e_f(i) and v_f(i) the number of edges and vertices, respectively, labeled i. We call f edge-friendly if |e_f(0) - e_f(1)| ≤ 1. Define the edge-balance index set of G as { |v_f(0) - v_f(1)| : the edge labeling f is edge-friendly}. We study the edge-balance index sets of generalized theta graphs.