Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài:On graphs with cyclic defect or excess. | On graphs with cyclic defect or excess Charles Delorme Laboratoire de Recherche en Informatique Universite Paris-Sud cd@lri.fr Guillermo Pineda-Villavicencio Centre for Informatics and Applied Optimization University of Ballarat work@guillermo.com.au Submitted Jun 16 2010 Accepted Oct 18 2010 Published Oct 29 2010 Mathematics Subject Classification 05C12 05C35 05C50 05C75 Abstract The Moore bound constitutes both an upper bound on the order of a graph of maximum degree d and diameter D k and a lower bound on the order of a graph of minimum degree d and odd girth g 2k 1. Graphs missing or exceeding the Moore bound by e are called graphs with defect or excess e respectively. While Moore graphs graphs with e 0 and graphs with defect or excess 1 have been characterized almost completely graphs with defect or excess 2 represent a wide unexplored area. Graphs with defect excess 2 satisfy the equation Gd k A Jn B Gd k A Jn B where A denotes the adjacency matrix of the graph in question n its order Jn the n X n matrix whose entries are all 1 s B the adjacency matrix of a union of vertex-disjoint cycles and Gd k x a polynomial with integer coefficients such that the matrix Gd k A gives the number of paths of length at most k joining each pair of vertices in the graph. In particular if B is the adjacency matrix of a cycle of order n we call the corresponding graphs graphs with cyclic defect or excess these graphs are the subject of our attention in this paper. We prove the non-existence of infinitely many such graphs. As the highlight of the paper we provide the asymptotic upper bound of O 64d3 2 for the number of graphs of odd degree d 3 and cyclic defect or excess. This bound is in fact quite generous and as a way of illustration we show the non-existence of some families of graphs of odd degree d 3 and cyclic defect or excess. Actually we conjecture that apart from the Mobius ladder on 8 vertices no non-trivial graph of any degree 3 and cyclic defect or excess exists. .
