tailieunhanh - Báo cáo toán học: "Maximum Degree Growth of the Iterated Line Graph"

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: Maximum Degree Growth of the Iterated Line Graph. | Maximum Degree Growth of the Iterated Line Graph Stephen G. Hartke Aparna W. Higginsy Department of Mathematics University of Dayton Dayton OH 45469-2316 Submitted February 25 1999 Accepted June 24 1999. Abstract Let Ak denote the maximum degree of the kth iterated line graph Lk G . For any connected graph G that is not a path the inequality Ak 1 2Ak 2 holds. Niepel Knor and Soltes 3 have conjectured that there exists an integer K such that for all k K equality holds that is the maximum degree Ak attains the greatest possible growth. We prove this conjecture using induced subgraphs of maximum degree vertices and locally maximum vertices. Mathematics Subject Classification Primary 05C75 Secondary 05C12. 1 Introduction The line graph L G of a graph G is defined as the graph whose vertices are the edges of G and where two vertices in L G are adjacent if and only if the corresponding edges in G are incident to a common vertex. Line graphs are well studied and we direct the reader to 1 for a general discussion of the properties of line graphs. In particular if v is a vertex in L G and u and w are the endpoints of the edge in G that corresponds to v then degL G v degG u degG w 2. Thus the maximum degree A L G of L G satisfies A L G 2A G 2 Correspondence to 3252 Greenmount Dr. Cincinnati OH 45248-3940 yemail higgins@ 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 6 1999 R28 2 and the minimum degree S L G satisfies Ổ L G 20 G - 2. The iterated line graph Lk G is defined recursively as L0 G G and Lk G L Lk-1 G for k 1. Though much is known about the line graph few results are known for the iterated line graph. Some of these results can be found in 2 . Using the inequalities above Niepel Knor and Soltés 3 developed the following bounds for the maximum degree Ak and minimum degree sk of the iterated line graph Lk G 2k ổo 2 2 Sk Ak A 2k Ao 2 2. Thus the maximum and minimum degree both have order 0 2k . Niepel et al. have conjectured that the maximum degrees of all