2017/01/20 by Arash Ahadi, Ali Dehghan, Ahadi, Arash +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1701.05934
A graph G is it weakly semiregular if there are two numbers a,b, such\nthat the degree of every vertex is a or b. The it weakly semiregular\nnumber of a graph G, denoted by wr(G), is the minimum number of subsets\ninto which the edge set of G can be partitioned so that the subgraph induced\nby each subset is a weakly semiregular graph. We present a polynomial time\nalgorithm to determine whether the weakly semiregular number of a given tree is\ntwo. On the other hand, we show that determining whether wr(G) = 2 for a\ngiven bipartite graph G with at most three numbers in its degree set is\n bf NP-complete. Among other results, for every tree T, we show that\nwr(T)\≤ 2\log2 \Δ(T) + \O(1), where \Δ(T) denotes the\nmaximum degree of T. In the second part of the work, we consider the\nrepresentation number. A graph G has a it representation modulo r if\nthere exists an injective map \ℓ: V (G) \→ \ℤr such that\nvertices v and u are adjacent if and only if |\ℓ(u) -\ℓ(v)| is\nrelatively prime to r. The it representation number, denoted by rep(G),\nis the smallest r such that G has a representation modulo r. Narayan and\nUrick conjectured that the determination of rep (G) for an arbitrary graph\nG is a difficult problem citenarayan2007representations. In this work, we\nconfirm this conjecture and show that if \NP\≠ P, then for any\n\ε >0, there is no polynomial time\n(1-\ε)\(n)/(2)-approximation algorithm for the computation of\nrepresentation number of regular graphs with n vertices.\n