Algorithmic complexity of weakly semiregular partitioning and the representation number

DOI10.1016/J.TCS.2017.01.028zbMATH Open1369.68224arXiv1701.05934OpenAlexW2963515165MaRDI QIDQ528476FDOQ528476

Mohsen Mollahajiaghaei, A. Ahadi, A. Dehghan

Publication date: 12 May 2017

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

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.

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

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

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)

Cites Work

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

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)