首页 | 本学科首页   官方微博 | 高级检索  
     


On island sequences of labelings with a condition at distance two
Authors:Sarah Spence Adams  Bradford Westgate
Affiliation:a Franklin W. Olin College of Engineering, Olin Way, Needham, MA 02492, USA
b Mathematics and Sciences Division, Babson College, Babson Park, MA 02457, USA
c School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14853, USA
Abstract:An L(2,1)-labeling of a graph G is a function f from the vertex set of G to the set of nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1, and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between the pair of vertices x,y. The lambda number of G, denoted λ(G), is the minimum range of labels used over all L(2,1)-labelings of G. An L(2,1)-labeling of G which achieves the range λ(G) is referred to as a λ-labeling. A hole of an L(2,1)-labeling is an unused integer within the range of integers used. The hole index of G, denoted ρ(G), is the minimum number of holes taken over all its λ-labelings. An island of a given λ-labeling of G with ρ(G) holes is a maximal set of consecutive integers used by the labeling. Georges and Mauro [J.P. Georges, D.W. Mauro, On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] inquired about the existence of a connected graph G with ρ(G)≥1 possessing two λ-labelings with different ordered sequences of island cardinalities. This paper provides an infinite family of such graphs together with their lambda numbers and hole indices. Key to our discussion is the determination of the path covering number of certain 2-sparse graphs, that is, graphs containing no pair of adjacent vertices of degree greater than 2.
Keywords:  mmlsi50"   onclick="  submitCitation('/science?_ob=MathURL&  _method=retrieve&  _eid=1-s2.0-S0166218X09003321&  _mathId=si50.gif&  _pii=S0166218X09003321&  _issn=0166218X&  _acct=C000054348&  _version=1&  _userid=3837164&  md5=ec7d7f386f774d36b002c5eb5d103a4f')"   style="  cursor:pointer  "   alt="  Click to view the MathML source"   title="  Click to view the MathML source"  >  formulatext"   title="  click to view the MathML source"  >L(2,1)-labeling     mmlsi51"   onclick="  submitCitation('/science?_ob=MathURL&  _method=retrieve&  _eid=1-s2.0-S0166218X09003321&  _mathId=si51.gif&  _pii=S0166218X09003321&  _issn=0166218X&  _acct=C000054348&  _version=1&  _userid=3837164&  md5=324f95dd574c5e3e07c41d749749f37d')"   style="  cursor:pointer  "   alt="  Click to view the MathML source"   title="  Click to view the MathML source"  >  formulatext"   title="  click to view the MathML source"  >L(2,1)-coloring   Hole index   Path covering number
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号