Algorithmic complexity of weakly semiregular partitioning and the representation number

DOI10.1016/J.TCS.2017.01.028MaRDI QIDQ528476zbMATH OpenOpenAlexFDO

Authors A. Ahadi, A. Dehghan, Mohsen Mollahajiaghaei

Publication date 12 May 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.05934

zbMATH Keywords

locally irregular graphrepresentation numberedge-partition problemssemiregular numberweakly semiregular number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 {�f NP}-complete. Among other results, for every tree $T$, we show that $wr(T)leq2lo{g}_{2}Delta(T)+mathcalO(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)ightarrowmathbb{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 $mathbfNPeqP$, then for any $epsilon>0$, there is no polynomial time $(1-epsilon)fracn2$-approximation algorithm for the computation of representation number of regular graphs with $n$ vertices.

Recommendations

• On the complexity of deciding whether the regular number is at most two
• The regular number of a graph
• Representation numbers of complete multipartite graphs
• Complexity of finding maximum regular induced subgraphs with prescribed degree
• Semiregular graphs and their algebra

Cites work

• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 1990001 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Algorithmic complexity of proper labeling problems
• An algorithmic proof of Tutte's f-factor theorem
• Computation of lucky number of planar graphs is NP-hard
• Covering planar graphs with forests
• Covering planar graphs with forests, one having bounded maximum degree
• Decomposing graphs into a constant number of locally irregular subgraphs
• Edge-partitioning graphs into regular and locally irregular components
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Graph factors and factorization: 1985--2003: a survey
• On a \(1,2\) conjecture
• On a directed variation of the 1-2-3 and 1-2 conjectures
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• On decomposing regular graphs into locally irregular subgraphs
• On the Complexity of General Graph Factor Problems
• On the Decomposition of Graphs
• On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs
• On the complexity of deciding whether the regular number is at most two
• On the complexity of determining the irregular chromatic index of a graph
• On the connectivity of semiregular cages
• On the unitary Cayley graphs of matrix algebras
• Orthogonal latin square graphs
• Regular number of a graph
• Representation numbers of complete multipartite graphs
• Representations of graphs and orthogonal latin square graphs
• Representations of graphs modulo n
• Representations of graphs modulo \(n\)
• Representations of split graphs, their complements, stars, and hypercubes
• Sequence variations of the 1-2-3 conjecture and irregularity strength
• Some properties of semiregular cages
• The NP-Completeness of Edge-Coloring
• The NP-Completeness of Some Edge-Partition Problems
• The complexity of \(P_{4}\)-decomposition of regular graphs and multigraphs
• The inapproximability for the \((0,1)\)-additive number
• The regular number of a graph
• Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs

This page was built for publication: Algorithmic complexity of weakly semiregular partitioning and the representation number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528476)