Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Vector spaces and the Petersen graph. | Vector spaces and the Petersen graph Marcelo H. de Carvalhoy UFMS Campo Grande Brasil C. H. C. Littlez Massey University Palmerston North New Zealand Submitted Aug 21 2006 Accepted Dec 17 2007 Published Jan 1 2008 Mathematics Subject Classification 05C70 Abstract It is shown that a matching covered graph has an ear decomposition with no more than one double ear if and only if there is no set S of edges such that S A is even for every alternating circuit A but S C is odd for some even circuit C. Two proofs are presented. The first uses vector spaces and the second is constructive. Some applications are also given. 1 Introduction Look at the Petersen graph drawn below. The set S e2 e4 e15g of edges has the following property S AI is even for each alternating circuit A but there is an even circuit C such as e2 63 e4 e10 615 e7g for which S CI is odd. Bricks for which the underlying simple graph is the Petersen graph are the only bricks that have such a set S. This paper reveals why. We present two arguments. The first uses vector spaces and is based on Lovasz s formula for the dimension of the linear space over GF 2 generated by the 1-factors of a matching covered graph. The second argument constructs S in those matching covered graphs in which it exists. We now present the relevant definitions notation and background. The vertex and edge sets of a graph G are denoted by VG and EG respectively. A 1-factor of G is the edge set of a regular spanning subgraph of degree 1. A connected graph is matching covered if every edge has a 1-factor containing it. Any such graph with more than two vertices is necessarily 2-connected. A graph G is said to be bicritical if G u vg has a 1-factor for -Supported by ProNEx - FAPESP proc. 2003 09925-5 CNPq proc. 478470 2006-1 04-4 620171 2006-5 and 471745 2007-3 and FUNDECT-MS. ySupported by CNPq Brasil. z Work done during this author s visit to UFMS Brasil in 2006 with support from CNPq. THE ELECTRONIC JOURNAL OF COMBINATORICS 15
