Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "On regular factors in regular graphs with small radius"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: On regular factors in regular graphs with small radius. | On regular factors in regular graphs with small radius Arne Hoffmann Lehrstuhl C fur Mathematik RWTH-Aachen 52056 Aachen Germany hoffmann@mathc.rwth-aachen.de Lutz Volkmann Lehrstuhl II fur Mathematik RWTH-Aachen 52056 Aachen Germany volkm@math2.rwth-aachen.de Submitted Aug 21 2001 Accepted Nov 5 2003 Published Jan 2 2004 MR Subject Classifications 05C70 05C35 Abstract In this note we examine the connection between vertices of high eccentricity and the existence of fc-factors in regular graphs. This leads to new results in the case that the radius of the graph is small 3 namely that a d-regular graph G has all fc-factors for fc V G even and fc d if it has at most 2d 2 vertices of eccentricity 3. In particular each regular graph G of diameter 3 has every fc-factor for fc V G even and fc d. 1 Introduction All graphs considered are finite and simple. We use standard graph terminology. For vertices u v E V G let d u v be the number of edges in a shortest path from u to v called the distance between u and v. Let further e v max d v x x E V G denote the eccentricity of x. The radius r G and the diameter dm G of a graph G are the minimum and maximum eccentricity respectively. If a graph G is disconnected then e v X for all vertices v in G. The complete graph with n vertices is denoted by Kn. For a set S Q V G let G S be the subgraph induced by S. In an r-almost regular graph the degrees of any two vertices differ by at most r. For b a 0 we call a subgraph F of G an a b -factor if V F V G and the degrees of all vertices in F are between a and b. We call a k k -factor simply a k-factor. If we do not say otherwise we quietly assume that k d if G is a d-regular graph. Many sufficient conditions for the existence of a k-factor in a regular graph are known today. Good surveys can be found in Akiyama and Kano 1 as well as Volkmann 8 . As far as we know none of these conditions have taken the eccentricity of vertices into corresponding author THE ELECTRONIC JOURNAL OF .