𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Factorisation of regular graphs into forests of short paths

✍ Scribed by Terri Lindquester; Nicholas C. Wormald

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
454 KB
Volume
186
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The k-linear arboricity of a graph G is the minimum number of forests whose connected components are paths of length at most k which partition E(G). Motivated by this index, we investigate a variation of this idea for d-regular graphs. Namely, we define a d-regular graph G to be (l,k)-linear arborific if E(G) can be partitioned into edge sets of l linear forests consisting of paths of length at most k. By extending an inductive tool developed by Jackson and Worrnald, we determine, for d/>4, values of k such that every d-regular graph is (d -1, k)-linear arborific. (~

πŸ“œ SIMILAR VOLUMES

Regular path decompositions of odd regul
Regular path decompositions of odd regular graphs
✍ Odile Favaron; FranΓ§ois Genest; Mekkia Kouider πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 197 KB

## Abstract Kotzig asked in 1979 what are necessary and sufficient conditions for a __d__‐regular simple graph to admit a decomposition into paths of length __d__ for odd __d__>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable

Factorization of regular multigraphs int
Factorization of regular multigraphs into regular graphs
✍ S. I. El-Zanati; M. J. Plantholt; S. K. Tipnis πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 618 KB

## Abstract A regular multigraph with maximum multiplicity __r__ and degree __rs__ cannot always be factored into __r s__‐regular simple graphs. It is shown, however, that under general conditions a similar factorization can be achieved if we first allow the addition or deletion of a relatively sma

Long path connectivity of regular graphs
Long path connectivity of regular graphs
✍ Cun-Quan Zhang; Yong-Jin Zhu πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 842 KB

Zhang, C.-Q. and Y.-J. Zhu, Long path connectivity of regular graphs, Discrete Mathematics 96 (1991) 151-160. Any pair of vertices in a 4-connected path or a path of length at least 3k-6. non-bipartite k-regular graph are joined bY a Hamilton \* This research was partially supported by AFOSR under g

Bandwidth of theta graphs with short pat
Bandwidth of theta graphs with short paths
✍ G.W. Peck; Aditya Shastri πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 628 KB

Peck, G.W. and A. Shastri, Bandwidth of theta graphs with short paths, Discrete Mathematics 103 (1992) 177-187. The bandwidth problem for a graph is that of labelling its vertices with distinct integers so that the maximum difference across an edge is minimized. We here solve this problem for all