On the irregularity of bipartite graphs
On the irregularity of bipartite graphs
复制标题
DOI：
10.1016/j.disc.2006.09.038
复制
发表时间：
2007-05-28
影响因子：
0.8
通讯作者：
Rautenbach, Dieter
中科院分区：
文献类型：
--
作者：
Henning, Michael A.;Rautenbach, Dieter
图G中边uv的不平衡性定义为竖线d（u）- d（v）竖线，其中d（u）表示u的度. G的不规则性，记为irr（G），是G中所有边的边不平衡之和。我们确定了具有最大可能的不规则性的二部图的结构与给定的基数的部集和给定的边缘数。然后，我们得到了相应的结果，与给定的基数的二部图的部集，并确定上界的不规则性，这些图。特别地，我们证明了：如果G是一个n阶二部图，其部集的基数相等，则irr（G）= 2n（2），则irr（G）
The imbalance of an edge uv in a graph G is defined as vertical bar d(u) - d(v)vertical bar, where d(u) denotes the degree of u. The irregularity of G, denoted irr(G), is the sum of the edge imbalances taken over all edges in G. We determine the structure of bipartite graphs having maximum possible irregularity with given cardinalities of the partite sets and given number of edges. We then derive a corresponding result for bipartite graphs with given cardinalities of the partite sets and determine an upper bound on the irregularity of these graphs. In particular, we show that if G is a bipartite graph of order n with partite sets of equal cardinalities, then irr (G) = 2n(2), then irr(G)