二分圖的譜半徑

一個方陣的譜半徑是指此方陣其特徵值最大的長度，而一個圖的譜半徑則是指此圖的鄰接矩陣的譜半徑。令G是個有e條邊且沒有孤立點的二分圖，已知G的譜半徑最多是sqrt{e}，而且達到此上界時若且唯若G是個完全二分圖，我們的第一個結果是延伸此結果當(e-1,e+1)不是一組雙生質數時，能去找到有e個邊，不是完全二分圖且擁有最大譜半徑的圖。 Bhattacharya、Friedland和Peled猜想當一個給定邊數e和兩部份的點數(p,q)且不是完全二分圖的二分圖，其能達到最大的譜半徑時，這個圖一定是完全二分圖再加上一個點和相應的邊數，我們找到了這個猜想的反例，並且猜測當我們把〝不是完全二分圖〞這個前提拿掉時，這個個較弱的猜想是對的。令p<=q，在e>=pq-q和p<=5時，我們證明了這個較弱的猜想。為了處理以上的問題，我們討論圖G的鄰接矩陣的平方C。更一般性地，對於一個非負矩陣C，藉由調整一個列中的值但使得此列的總和維持不變，我們發展出一套方法來找到一個非負矩陣的譜半徑的上下界，這個方法能讓我們很容易地得到許多已知的或新的上下界。

關鍵字

二分圖；鄰接矩陣；非負矩陣；譜半徑

並列摘要

The spectral radius of a square matrix C is the largest magnitude of an eigenvalue of C and the spectral radius of a graph G is the spectral radius of the adjacency matrix of G. Let G be a bipartite graph with e edges without isolated vertices. It was known that the spectral radius of G is at most the square root of e, and the upper bound is attained if and only if G is a complete bipartite graph. Our first result extends this result to find the maximum spectral radius of a non-complete bipartite graph with e edges under the assumption that (e - 1; e + 1) is not a pair of twin primes. Bhattacharya, Friedland and Peled conjectured that a non-complete bipartite graph which has the maximum spectral radius with given e and bi-order (p, q) is obtained from a complete bipartite graph by deleting edges incident to a common vertex. We find counter examples of this conjecture. Under the additional assumption e>=pq-q or under the assumption p<=5, where p<=q, we prove a weaker version of the above conjecture that drops the non-complete assumption of the bipartite graph. To handle the problem above, we study the spectral radius of a nonnegative matrix C which takes the square of the adjacency matrix of G as a special case. For a general nonnegative matrix C, we give a new approach to obtain lower bounds and upper bounds of the spectral radius of C which are the spectral radii of matrices obtained by suitably reweighting the entries in a row of C keeping the row-sum unchanged. This method helps us to find many spectral bounds of C easily.

並列關鍵字

bipartite graph ； adjacency matrix ； nonnegative matrix ； spectral radius

參考文獻

[1] J. C. Bermond, J. C. Fournier, M. Las Vergnas, D. Sotteau (Eds.), Problèmes Combinatoires et Theorie des Graphes, Orsay, 1976, Coll. Int. C.N.R.S., vol.260, C.N.R.S. Publ., 1978.