Factors and Factorizations of Graphs Proof Techniques in Factor Theo
This book chronicles the development of graph factors and factorizations. It pursues a comprehensive approach, addressing most of the important results from hundreds of findings over the last century. One of the main themes is the observation that many th
- PDF / 3,649,844 Bytes
- 362 Pages / 439.37 x 666.142 pts Page_size
- 22 Downloads / 178 Views
For further volumes: http://www.springer.com/series/304
2031
•
Jin Akiyama
•
Mikio Kano
Factors and Factorizations of Graphs Proof Techniques in Factor Theory
123
Jin Akiyama Tokai University Research Institute of Educational Development Tomigaya 2-28-4 151-8677 Shibuya-ku Japan [email protected]
Mikio Kano Ibaraki University Computer and Information Sciences Nakanarusawa Ibaraki-ken 316-8511 Hitachi Japan [email protected]
e-ISBN 978-3-642-21919-1 ISBN 978-3-642-21918-4 DOI 10.1007/978-3-642-21919-1 Springer Heidelberg Dordrecht London New York Lecture Notes in Mathematics ISSN print edition: 0075-8434 ISSN electronic edition: 1617-9692 Library of Congress Control Number: 2011932316 Mathematics Subject Classification (2010): 05C, 05CXX, 05C75 c Springer-Verlag Berlin Heidelberg 2011 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: deblik, Berlin Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
to Frank Harary, my teacher and to my wife Yoko
•
Preface
A spanning subgraph of a graph is its subgraph whose vertex set is the same as the original graph. In this book, spanning subgraphs of graphs possessing some given properties are studied, and these spanning subgraphs are called factors. For example, for a positive integer k, a k-factor of a graph is its spanning subgraph each of whose vertices has a constant degree k. So a 1factor is nothing but a perfect matching, where a matching in a graph G is a subgraph of G whose edges are pairwise disjoint and a perfect matching is a matching that covers all the vertices of G. Furthermore a 2-factor is a set of vertex-disjoint cycles which together cover the vertices of the graph. Similarly, a graph each of whose vertices has a constant degree k is called a k-regular graph, and if k is even, such a graph is said to be even regular. If the edges of a graph G can be decomposed into k-factors, then G is said to be k-factorable. Petersen’s results on graph factors and factorizations date back to the 19th century. Petersen’s Theorem, which he proved in order to solve a problem on Diophantine equations, states: Every even regular graph is 2-factorable. Petersen then went on to prove another theorem: Every 2-
Data Loading...
