Degree-bounded factorizations of bipartite multigraphs and of pseudographs |
| |
Authors: | AJW Hilton |
| |
Institution: | School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London, E1 4NS, England, United Kingdom Department of Mathematics, University of Reading, Whiteknights, Reading, RG6 6AX, England, United Kingdom |
| |
Abstract: | For d≥1, s≥0 a (d,d+s)-graph is a graph whose degrees all lie in the interval {d,d+1,…,d+s}. For r≥1, a≥0 an (r,r+a)-factor of a graph G is a spanning (r,r+a)-subgraph of G. An (r,r+a)-factorization of a graph G is a decomposition of G into edge-disjoint (r,r+a)-factors. A graph is (r,r+a)-factorable if it has an (r,r+a)-factorization.We prove a number of results about (r,r+a)-factorizations of (d,d+s)-bipartite multigraphs and of (d,d+s)-pseudographs (multigraphs with loops permitted). For example, for t≥1 let β(r,s,a,t) be the least integer such that, if d≥β(r,s,a,t) then every (d,d+s)-bipartite multigraph G is (r,r+a)-factorable with x(r,r+a)-factors for at least t different values of x. Then we show that |
| |
Keywords: | Factorizations Bipartite multigraphs Pseudographs _method=retrieve& _eid=1-s2 0-S0012365X08005852& _mathId=si44 gif& _pii=S0012365X08005852& _issn=0012365X& _acct=C000069490& _version=1& _userid=6211566& md5=a40d2ce4cac0d8f4920dafc4c30b123c')" style="cursor:pointer (a" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">(a b)-factorizations |
本文献已被 ScienceDirect 等数据库收录! |
|