QSpace Collection:
http://hdl.handle.net/1974/5942
2016-05-25T05:17:33ZHall conditions for edge-weighted bipartite graphs
http://hdl.handle.net/1974/5946
Title: Hall conditions for edge-weighted bipartite graphs
Authors: Gregory, David
Abstract: A weighted variant of Hall's condition for the existence of matchings is shown to
be equivalent to the existence of a matching in a lexicographic product.
This is used to introduce characterizations of those bipartite graphs whose edges may be replicated so as to yield semiregular multigraphs or, equivalently, semiregular edge-weightings. Such bipartite graphs will be called semiregularizable.
Some infinite families of semiregularizable trees are described and all semiregularizable trees on at most 11 vertices are listed.
Matrix analogues of some of the results are mentioned and are shown to imply some of the known characterizations of regularizable graphs.
Description: Notes based on seminar talks given at Queen's University and the Royal Military College, Kingston, 2009-10.2010-07-28T14:50:18Z