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

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

Mohsen Mollahajiaghaei, A. Dehghan

Publication date: 28 December 2016

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

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

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

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

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)

Cites Work

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

Cited In (2)

• A lower bound and several exact results on the \(d\)-lucky number
• Algorithmic complexity of weakly semiregular partitioning and the representation 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)