On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs

DOI10.1016/J.DAM.2016.10.028zbMATH Open1352.05068OpenAlexW2560469491MaRDI QIDQ730489FDOQ730489

Authors Mohsen Mollahajiaghaei, A. Dehghan

Publication date 28 December 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitycombinatorial Nullstellensatzclosed distinguishing labelinglist-closed distinguishing labelingstrong closed distinguishing labeling

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: An assignment of numbers to the vertices of graph G is closed distinguishing if for any two adjacent vertices v and u the sum of labels of the vertices in the closed neighborhood of the vertex v differs from the sum of labels of the vertices in the closed neighborhood of the vertex u unless they have the same closed neighborhood (i.e. N[u]=N[v]). The closed distinguishing number of G, denoted by dis[G], is the smallest integer k such that there is a closed distinguishing labeling for G using integers from the set[k].Also, for each vertex $vinV(G)$, let L(v) denote a list of natural numbers available at v. A list closed distinguishing labeling is a closed distinguishing labeling f such that $f(v)inL(v)$ for each $vinV(G)$.A graph G is said to be closed distinguishing k-choosable if every k-list assignment of natural numbers to the vertices of G permits a list closed distinguishing labeling of G. The closed distinguishing choice number of G, $di{s}_{ell}[G]$, is the minimum number k such that G is closed distinguishing k-choosable. We show that for each integer t there is a bipartite graph G such that $dis[G]>t$.It was shown that for every graph G with $Deltageq2$, $dis[G]leqdi{s}_{ell}[G]leqDelt{a}^2-Delta+1$ and there are infinitely values of $Delta$ for which G might be chosen so that $dis[G]=Delt{a}^2-Delta+1$. We show that the difference between $dis[G]$ and $di{s}_{ell}[G]$ can be arbitrary large and for every positive integer t there is a graph G such that $di{s}_{ell}[G]-dis[G]geqt$. We improve the current upper bound and give some number of upper bounds for the closed distinguishing choice number by using the Combinatorial Nullstellensatz. We show that it is $mathbfNP$-complete to decide for a given planar subcubic graph G, whether dis[G]=2. Also, we prove that for every $kgeq3$, it is {�f NP}-complete to decide whether $dis[G]=k$ for a given graph G

Recommendations

• A note on adjacent vertex distinguishing colorings of graphs
• List-distinguishing colorings of graphs
• On the algorithmic complexity of determining the AVD and NSD chromatic indices of graphs
• On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach
• Asymptotically optimal bound on the adjacent vertex distinguishing edge choice number

Cites work

• scientific article; zbMATH DE number 4094812 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• A new type of edge-derived vertex coloring
• A note on adjacent vertex distinguishing colorings of graphs
• Algorithmic complexity of proper labeling problems
• An oriented version of the 1-2-3 conjecture
• Bounding the monomial index and \((1,l)\)-weight choosability of a graph
• Colorings and orientations of graphs
• Digraphs are 2-weight choosable
• Edge weights and vertex colours
• Locally identifying coloring in bounded expansion classes of graphs
• Locally identifying coloring of graphs
• Locally identifying colourings for graphs with given maximum degree
• On a \(1,2\) conjecture
• On strongly planar not-all-equal 3SAT
• On the 1-2-3-conjecture
• On the complexity of vertex-coloring edge-weightings
• Relaxed locally identifying coloring of graphs
• Sequence variations of the 1-2-3 conjecture and irregularity strength
• Total weight choosability of Cartesian product of graphs
• Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
• Vertex-colouring edge-weightings with two edge weights
• Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs
• Weight choosability of graphs

Cited in

(2)

• Algorithmic complexity of weakly semiregular partitioning and the representation number
• A lower bound and several exact results on the \(d\)-lucky number

This page was built for publication: On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs

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