Queen's University - Utility Bar

QSpace at Queen's University >
Mathematics and Statistics, Department of >
Department of Mathematics and Statistics Faculty Publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1974/5946

Title: Hall conditions for edge-weighted bipartite graphs
Authors: Gregory, David

Files in This Item:

File Description SizeFormat
HallConditions_2010_07_20.pdf187.18 kBAdobe PDFView/Open
Keywords: Hall's theorem, bipartite multigraphs, regular, semiregular
Issue Date: 2010
Series/Report no.: Seminar
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.
URI: http://hdl.handle.net/1974/5946
Appears in Collections:Department of Mathematics and Statistics Faculty Publications

This item is licensed under a Creative Commons License
Creative Commons

Items in QSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


  DSpace Software Copyright © 2002-2008  The DSpace Foundation - TOP