Loading...

On the Complexity of Deciding Whether the Regular Number is at Most Two

Dehghan, A ; Sharif University of Technology

473 Viewed
  1. Type of Document: Article
  2. DOI: 10.1007/s00373-014-1446-9
  3. Abstract:
  4. The regular number of a graph (Formula presented.) denoted by (Formula presented.) is the minimum number of subsets into which the edge set of (Formula presented.) can be partitioned so that the subgraph induced by each subset is regular. In this work we answer to the problem posed as an open problem in Ganesan et al. (J Discrete Math Sci Cryptogr 15(2-3):49-157, 2012) about the complexity of determining the regular number of graphs. We show that computation of the regular number for connected bipartite graphs is NP-hard. Furthermore, we show that, determining whether (Formula presented.) for a given connected (Formula presented.)-colorable graph (Formula presented.) is NP-complete. Also, we prove that a new variant of the Monotone Not-All-Equal 3-Sat problem is NP-complete
  5. Keywords:
  6. Computational complexity ; Edge-partition problems ; Not-All-Equal 3-Sat ; Regular number
  7. Source: Graphs and Combinatorics ; Volume 31, Issue 5 , September , 2014 , pp 1359-1365 ; ISSN: 09110119
  8. URL: http://link.springer.com/article/10.1007%2Fs00373-014-1446-9