Algorithmic complexity of weakly semiregular partitioning and the representation number

作者：Ahadi Arash; Dehghan Ali^*; Mollahajiaghaei Mohsen

来源：Theoretical Computer Science, 2017, 674: 60-72.

DOI：10.1016/j.tcs.2017.01.028

• Weakly semiregular number
• Semiregular number
• Edge-partition problems
• Locally irregular graph
• Representation number

A graph G is weakly semiregular if there are two numbers a, b, such that the degree of every vertex is a or b. The 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 NP-complete. Among other results, for every tree T, we show that wr(T) <= 2 log(2) Delta(T) + O(1), where (T) denotes the maximum degree of T. A graph G is a [d, d + s]-gTaph if the degree of every vertex of G lies in the interval [d, d + s]. A [d, d + 1]-graph is said to be semiregular. The semiregular number of a graph G, denoted by sr(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 semiregular graph. We prove that the semiregular number of a tree T is [Delta(T)/2]. On the other hand, we show that determining whether sr(G) = 2 for a given bipartite graph G with Delta(G) <= 6 is NP-complete. In the second part of the work, we consider the representation number. A graph G has a representation modulo r if there exists an injective map l : V (G) -> Z(r) such that vertices v and u are adjacent if and only if vertical bar l(u) - l(v)vertical bar is relatively prime to r. The 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 [38]. In this work, we confirm this conjecture and show that if NP not equal P, then for any is an element of > 0, there is no polynomial time (1 - is an element of)n/2-approximationalgorithm for the computation of representation number of regular graphs with n vertices.

• 出版日期2017-4-25