ON LOCALLY-BALANCED 2-PARTITIONS OF BIPARTITE GRAPHS

Authors

  • Aram H. Gharibyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia
  • Petros A. Petrosyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2020.54.3.137

Keywords:

locally-balanced 2-partition, NP-completeness, bipartite graph, biregular bipartite graph, subcubic bipartite graph

Abstract

A \emph{$2$-partition of a graph $G$} is a function $f:V(G)\rightarrow \{0,1\}$. A $2$-partition $f$ of a graph $G$ is a \emph{locally-balanced with an open neighborhood}, if for every $v\in V(G)$, $\left\vert \vert \{u\in N_{G}(v)\colon\,f(u)=0\}\vert - \vert \{u\in N_{G}(v)\colon\,f(u)=1\}\vert \right\vert\leq 1$. A bipartite graph is \emph{$(a,b)$-biregular} if all vertices in one part have degree $a$ and all vertices in the other part have degree $b$. In this paper we prove that the problem of deciding, if a given graph has a locally-balanced $2$-partition with an open neighborhood is $NP$-complete even for $(3,8)$-biregular bipartite graphs. We also prove that a $(2,2k+1)$-biregular bipartite graph has a locally-balanced $2$-partition with an open neighbourhood if and only if it has no cycle of length $2 \pmod{4}$. Next, we prove that if $G$ is a subcubic bipartite graph that has no cycle of length $2 \pmod{4}$, then $G$ has a locally-balanced $2$-partition with an open neighbourhood. Finally, we show that all doubly convex bipartite graphs have a locally-balanced $2$-partition with an open neighbourhood.

Downloads

Published

2020-12-15

How to Cite

Gharibyan, A. H., & Petrosyan, P. A. (2020). ON LOCALLY-BALANCED 2-PARTITIONS OF BIPARTITE GRAPHS. Proceedings of the YSU A: Physical and Mathematical Sciences, 54(3 (253), 137–145. https://doi.org/10.46991/PYSU:A/2020.54.3.137

Issue

Section

Mathematics