Bipartite Graphs with Balanced $(a,b)$-Partitions

Abstract

In this paper, we will be concerned with graphs $G$ satisfying: $G$ is isometrically embeddable in a hypercube; $|C(a,b)|=|C(b,a)|$ for every edge $[a,b]$ of $G$. where $C(a,b)$ is the set of vertices nearer to $a$ than to $b$. Some properties of such graphs are shown; in particular, it is shown that all such graphs $G$ are $3$-connected if $G$ has at least two edges and $G$ is not a cycle.