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


Covering graphs with matchings of fixed size
Authors:David Cariolaro  Hung-Lin Fu
Affiliation:a Institute of Mathematics, Academia Sinica, Nankang, Taipei 11529, Taiwan
b Department of Applied Mathematics, National Chiao Tung University, Hsin Chu 30050, Taiwan
Abstract:Let m be a positive integer and let G be a graph. We consider the question: can the edge set E(G) of G be expressed as the union of a set M of matchings of G each of which has size exactly m? If this happens, we say that G is [m]-coverable and we call M an [m]-covering of G. It is interesting to consider minimum[m]-coverings, i.e. [m]-coverings containing as few matchings as possible. Such [m]-coverings will be called excessive[m]-factorizations. The number of matchings in an excessive [m]-factorization is a graph parameter which will be called the excessive[m]-index and denoted by View the MathML source. In this paper we begin the study of this new parameter as well as of a number of other related graph parameters.
Keywords:Excessive   mmlsi29"   onclick="  submitCitation('/science?_ob=MathURL&  _method=retrieve&  _eid=1-s2.0-S0012365X08005773&  _mathId=si29.gif&  _pii=S0012365X08005773&  _issn=0012365X&  _acct=C000053510&  _version=1&  _userid=1524097&  md5=2799d2e1de35f721cdb4e772e9532224')"   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"  >[m]-factorization   Excessive   mmlsi30"   onclick="  submitCitation('/science?_ob=MathURL&  _method=retrieve&  _eid=1-s2.0-S0012365X08005773&  _mathId=si30.gif&  _pii=S0012365X08005773&  _issn=0012365X&  _acct=C000053510&  _version=1&  _userid=1524097&  md5=4be81f1a08e360e2bbbd2e63e762fb92')"   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"  >[m]-index     mmlsi31"   onclick="  submitCitation('/science?_ob=MathURL&  _method=retrieve&  _eid=1-s2.0-S0012365X08005773&  _mathId=si31.gif&  _pii=S0012365X08005773&  _issn=0012365X&  _acct=C000053510&  _version=1&  _userid=1524097&  md5=a82b8aa5218184198d6a376421a0b18c')"   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"  >[m]-covering
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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