Showing cs.DMShow all
2 papers · 1 filter
cs.DM2018
On the algorithmic complexity of decomposing graphs into regular/irregular structures
Arash Ahadi, Ali Dehghan, Mohammad-Reza Sadeghi +1
A locally irregular graph is a graph whose adjacent vertices have distinct degrees, a regular graph is a graph where each vertex has the same degree and a locally regular graph is…
cs.DM2018
Not-All-Equal and 1-in-Degree Decompositions: Algorithmic Complexity and Applications
Ali Dehghan, Mohammad-Reza Sadeghi, Arash Ahadi
A Not-All-Equal (NAE) decomposition of a graph is a decomposition of the vertices of into two parts such that each vertex in has at least one neighbor in each part. Als…