Unoriented Laplacian maximizing graphs are degree maximal
Unoriented Laplacian maximizing graphs are degree maximal
复制标题
无向拉普拉斯最大化图的度数最大
DOI：
10.1016/j.laa.2008.04.002
复制
发表时间：
2008-08
影响因子：
1.1
通讯作者：
Zhou, Jun
中科院分区：
文献类型：
--
作者：
Tam, Bit-Shun;Fan, Yi-Zheng;Zhou, Jun
一个连通图称为无向Laplacian极大化图，如果它的无向Laplacian矩阵的谱半径在所有顶点数和边数相同的连通图中达到最大值.如果一个图的度序列不被任何其他图的度序列优化（并且，另外，该图是连通的），则称该图是阈值（最大）的。证明了一个无向Laplacian极大图是极大图，并且存在两个给定阶且零度为3的无向Laplacian极大图。我们的处理依赖于以下已知的特征：图G是阈值（极大）的当且仅当对于G的每对顶点u，v，集合N（u）<${v}，N（v）<${u}，其中N（u）表示G中u的邻居集，关于包含关系是可比较的（并且，此外，图是连通的）。本文还提出了一个关于图的无向拉普拉斯矩阵在顶点数和边数相同的图中最大化的猜想。
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.
登录
查看更多内容
DOI：
10.1007/1-4020-2721-4_1
发表时间：
2011-04
期刊：
--
影响因子：
--
作者：
B. Ya
通讯作者：
B. Ya
影响因子：
1.1
作者：
Xiaodong Zhang;Rong Luo
通讯作者：
Xiaodong Zhang;Rong Luo
DOI：
10.1016/s0167-5060(13)71063-x
发表时间：
1995
期刊：
--
影响因子：
--
作者：
N. Mahadev;U. Peled
通讯作者：
N. Mahadev;U. Peled
影响因子：
1.1
作者：
Yaoping Hou;Jiongsheng Li;Yong-Liang Pan
通讯作者：
Yaoping Hou;Jiongsheng Li;Yong-Liang Pan
DOI：
10.1007/bf00390110
发表时间：
1986-06
期刊：
Order
影响因子：
--
作者：
R. Möhring
通讯作者：
R. Möhring