Premium
Factorization of regular multigraphs into regular graphs
Author(s) -
ElZanati S. I.,
Plantholt M. J.,
Tipnis S. K.
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190190110
Subject(s) - multigraph , mathematics , combinatorics , factorization , multiplicity (mathematics) , simple (philosophy) , simple graph , graph , discrete mathematics , algorithm , mathematical analysis , philosophy , epistemology
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 small number of hamilton cycles. Based on this result, we give extensions of some known factorization results on simple graphs to new results on multigraphs. © 1995 John Wiley & Sons, Inc.