Unoriented Laplacian maximizing graphs are degree maximal |
| |
Authors: | Bit-Shun Tam Yi-Zheng Fan Jun Zhou |
| |
Affiliation: | a Department of Mathematics, Tamkang University, Tamsui 251, Taiwan, ROC b School of Mathematics and Computation Sciences, Anhui University, Heifei, Anhui 230039, PR China |
| |
Abstract: | A connected graph is said to be unoriented Laplacian maximizing if the spectral radius of its unoriented Laplacian matrix attains the maximum among all connected graphs with the same number of vertices and the same number of edges. A graph is said to be threshold (maximal) if its degree sequence is not majorized by the degree sequence of any other graph (and, in addition, the graph is connected). It is proved that an unoriented Laplacian maximizing graph is maximal and also that there are precisely two unoriented Laplacian maximizing graphs of a given order and with nullity 3. Our treatment depends on the following known characterization: a graph G is threshold (maximal) if and only if for every pair of vertices u,v of G, the sets N(u)?{v},N(v)?{u}, where N(u) denotes the neighbor set of u in G, are comparable with respect to the inclusion relation (and, in addition, the graph is connected). A conjecture about graphs that maximize the unoriented Laplacian matrix among all graphs with the same number of vertices and the same number of edges is also posed. |
| |
Keywords: | 05C50 15A18 |
本文献已被 ScienceDirect 等数据库收录! |
|