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: Vertex subsets with minimal width and dual width in Q-polynomial distance-regular graphs. | Vertex subsets with minimal width and dual width in Q-polynomial distance-regular graphs Hajime Tanaka Department of Mathematics University of Wisconsin 480 Lincoln Drive Madison WI 53706 . htanaka@ Submitted Nov 8 2010 Accepted Aug 4 2011 Published Aug 19 2011 Mathematics Subject Classifications 05E30 06A12 Abstract We study Q-polynomial distance-regular graphs from the point of view of what we call descendents that is to say those vertex subsets with the property that the width w and dual width w satisfy w w d where d is the diameter of the graph. We show among other results that a nontrivial descendent with w 2 is convex precisely when the graph has classical parameters. The classification of descendents has been done for the 5 classical families of graphs associated with short regular semilattices. We revisit and characterize these families in terms of posets consisting of descendents and extend the classification to all of the 15 known infinite families with classical parameters and with unbounded diameter. 1 Introduction Q-polynomial distance-regular graphs are thought of as finite combinatorial analogues of compact symmetric spaces of rank one and are receiving considerable attention see . 2 3 15 25 and the references therein. In this paper we study these graphs further from the point of view of what we shall call descendents that is to say those vertex subsets with the property that the width w and dual width w satisfy w w d where d is the diameter of the graph. See 2 for formal definitions. A typical example is a w-cube H w 2 in the d-cube H d 2 w d . The width and dual width of subsets were introduced and discussed in detail by Brouwer Godsil Koolen and Martin 4 and descendents arise as a special but very important case of the theory 4 5 . They showed among other results that every descendent Regular address Graduate School of Information Sciences Tohoku University 6-3-09 Aramaki-Aza-Aoba Aoba-ku Sendai 980-8579 Japan THE .
