A note on adjacent vertex distinguishing colorings of graphs

详细信息    查看全文

• 作者：M. Axenovich^a ; ^{maria.aksenovich@kit.edu" class="auth_mail" title="E-mail the corresponding author} ; J. Harant^b ; ^{jochen.harant@tu-ilmenau.de" class="auth_mail" title="E-mail the corresponding author} ; J. Przybyło^c ; ^{przybylo@wms.mat.agh.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; R. Sotá ; k^d ; ^{roman.sotak@upjs.sk" class="auth_mail" title="E-mail the corresponding author} ; M. Voigt^e ; ^{mvoigt@informatik.htw-dresden.de" class="auth_mail" title="E-mail the corresponding author} ; J. Weidelich^a ; ^{jennyweidelich@web.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Vertex-distinguishing ; Labeling ; Coloring ; List-vertex-distinguishing
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 May 2016
• 年：2016
• 卷：205
• 期：Complete
• 页码：1-7
• 全文大小：391 K

文摘

For an assignment of numbers to the vertices of a graph, let class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si3.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=d86c00c0654691b508fe36cd13d69006" title="Click to view the MathML source">S[u]class="mathContainer hidden">class="mathCode">$S\left[u\right]$ be the sum of the labels of all the vertices in the closed neighborhood of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si4.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=d32b5874dfb636652714535ff62366f9" title="Click to view the MathML source">uclass="mathContainer hidden">class="mathCode">$u$, for a vertex class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si4.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=d32b5874dfb636652714535ff62366f9" title="Click to view the MathML source">uclass="mathContainer hidden">class="mathCode">$u$. Such an assignment is called closed distinguishing   if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si6.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=b6e709822a1c9cc285d9eefa12d7f76b" title="Click to view the MathML source">S[u]≠S[v]class="mathContainer hidden">class="mathCode">$S\left[u\right]\ne S\left[v\right]$ for any two adjacent vertices class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si4.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=d32b5874dfb636652714535ff62366f9" title="Click to view the MathML source">uclass="mathContainer hidden">class="mathCode">$u$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si8.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=50bdf32e0a632b0be6ee5328dd524a9a" title="Click to view the MathML source">vclass="mathContainer hidden">class="mathCode">$v$ unless the closed neighborhoods of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si4.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=d32b5874dfb636652714535ff62366f9" title="Click to view the MathML source">uclass="mathContainer hidden">class="mathCode">$u$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si8.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=50bdf32e0a632b0be6ee5328dd524a9a" title="Click to view the MathML source">vclass="mathContainer hidden">class="mathCode">$v$ coincide. In this note we investigate class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si11.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=2e7d3b15038063fd821d2f5af74361f0">class="imgLazyJSB inlineImage" height="15" width="41" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15005740-si11.gif">class="mathContainer hidden">class="mathCode">$\mathrm{dis}\left[G\right]$, the smallest integer class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si12.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=fae37be7870e8fe74e6a12f4482b4219" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$ such that there is a closed distinguishing labeling of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si13.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=c26c744fabf173dafed02a122fd65d99" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ using labels from class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si14.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=cf084c0a772dc2d3565e1f08380d7a28" title="Click to view the MathML source">{1,…,k}class="mathContainer hidden">class="mathCode">$\{1,\dots ,k\}$. We prove that class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si15.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=5d4051385af5ba096bece079652cc4c5">class="imgLazyJSB inlineImage" height="17" width="143" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15005740-si15.gif">class="mathContainer hidden">class="mathCode">$\mathrm{dis}\left[G\right]\le {\Delta }^2-\Delta +1$, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si16.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=7fb9fc61b41744e90f2a951cd75358b2" title="Click to view the MathML source">Δclass="mathContainer hidden">class="mathCode">$\Delta$ is the maximum degree of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si13.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=c26c744fabf173dafed02a122fd65d99" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$. This result is sharp. We also consider a list-version of the function class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005740&_mathId=si11.gif&_user=111111111&_pii=S0166218X15005740&_rdoc=1&_issn=0166218X&md5=2e7d3b15038063fd821d2f5af74361f0">class="imgLazyJSB inlineImage" height="15" width="41" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15005740-si11.gif">class="mathContainer hidden">class="mathCode">$\mathrm{dis}\left[G\right]$ and give a number of related results.