Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
We propose two alternative measures of the local irregularity of a graph in terms of its vertex degrees and relate these measures to the order and the global irregularity of the graph measured by the difference of its maximum and minimum vertex degree.All graphs will be simple and finite. Let G = (V,E) be a graph of order n = |V |. The degree and the neighbourhood of a vertex u 2 V will be denoted by d(u) and N(u). The maximum and minimum degree of G will be denoted by (G) and (G). | Propagation of mean degrees Dieter Rautenbach Forschungsinstitut fur Diskrete Mathematik Universitat Bonn Lennestr. 2 D-53113 Bonn Germany rauten@or.uni-bonn.de Submitted May 6 2002 Accepted Jul 29 2003 Published Jul 26 2004 MR Subject Classifications 05C35 05C99 Abstract We propose two alternative measures of the local irregularity of a graph in terms of its vertex degrees and relate these measures to the order and the global irregularity of the graph measured by the difference of its maximum and minimum vertex degree. 1 Introduction All graphs will be simple and finite. Let G V E be a graph of order n V . The degree and the neighbourhood of a vertex u E V will be denoted by d u and N u . The maximum and minimum degree of G will be denoted by A G and 8 G . A graph G is usually called regular if A G 8 G which trivially implies that d u d v for all edges uv E E. In view of this convention we considered in 5 the expressions A G 8 G and max d u d v l uv E E as suitable measures of the global and local irregularity of G respectively. The main results of 5 are asymptotically tight lower bounds on the order of a connected graph in terms of its global and local irregularity. The intuition behind these bounds is that the global irregularity of a connected graph with bounded local irregularity can only be large if its order is large. Following suggestions of M. Kouider and J.-F. Sacle 3 we will consider here two alternative measures of local irregularity. Again our main results relate the order of the graph its global irregularity and one of these measures. A reasonable requirement for a possible measure of local irregularity is that it should be zero for a connected graph if and only if the global irregularity is zero. It is easy to see that A G 8 G 0 for a connected graph G if and only if X d v d u 0 for every u E V 1 veN u THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 N11 1 or -rà X d u N u d v d u 0 for every u E V. 2 The terms in 1 and 2 are the total and the mean .
