Premium
Isomorphic Factorization of Regular Graphs and 3‐Regular Multigraphs
Author(s) -
Ellingham M. N.,
Wormald N. C.
Publication year - 1988
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-37.121.14
Subject(s) - multigraph , combinatorics , mathematics , edge coloring , graph , discrete mathematics , mathematical proof , set (abstract data type) , line graph , computer science , graph power , geometry , programming language
A multigraph G is divisible by t if its edge set can be partitioned into t subsets, such that the subgraphs (called factors ) induced by the subsets are all isomorphic. If G has e ( G ) edges, then it is t‐rational if it is divisible by t or if t does not divide e ( G ). A short proof is given that any graph G is t ‐rational for all t ⩾ ξ′( G ) (the chromatic index of G ), and thus any r ‐regular graph is t ‐rational for all t ⩾ r +1. The main result of this paper is that all 3‐regular multigraphs are divisible by 3, in such a way that the components of each factor are paths of length 1 or 2. It follows that 3‐regular graphs are t ‐rational for all t ⩾ 3. The proofs rely on edge‐colouring techniques.