Algorithmic Complexity of Weakly Semiregular Partitioning and the Representation Number

Abstract

A graph $G$ is {\it weakly semiregular} if there are two numbers $a,b$, such that the degree of every vertex is $a$ or $b$. The {\it weakly semiregular number} of a graph $G$, denoted by $wr(G)$, is the minimum number of subsets into which the edge set of $G$ can be partitioned so that the subgraph induced by each subset is a weakly semiregular graph. We present a polynomial time algorithm to determine whether the weakly semiregular number of a given tree is two. On the other hand, we show that determining whether $wr(G)=2$ for a given bipartite graph $G$ with at most three numbers in its degree set is {\bf NP}-complete. Among other results, for every tree $T$, we show that $wr(T)\le 2{\log }_2\Delta (T)+\mathcal{O}(1)$, where $\Delta (T)$ denotes the maximum degree of $T$. In the second part of the work, we consider the representation number. A graph $G$ has a {\it representation modulo $r$} if there exists an injective map $\ell :V(G)\to {\mathbb{Z}}_r$ such that vertices $v$ and $u$ are adjacent if and only if $|\ell (u)-\ell (v)|$ is relatively prime to $r$. The {\it representation number}, denoted by $rep(G)$, is the smallest $r$ such that $G$ has a representation modulo $r$. Narayan and Urick conjectured that the determination of $rep(G)$ for an arbitrary graph $G$ is a difficult problem \cite{narayan2007representations}. In this work, we confirm this conjecture and show that if $\mathbf{NP}\ne \mathbf{P}$, then for any $\epsilon >0$, there is no polynomial time $(1-\epsilon )\frac{n}{2}$-approximation algorithm for the computation of representation number of regular graphs with $n$ vertices.

To appear in Theoretical Computer Science