1 |
Spectral threshold dominance, Brouwer's conjecture and maximality of Laplacian energyHelmberg, Christoph, Trevisan, Vilmar 11 June 2015 (has links) (PDF)
The Laplacian energy of a graph is the sum of the distances of the eigenvalues of the Laplacian matrix of the graph to the graph's average degree. The maximum Laplacian energy over all graphs on n nodes and m edges is conjectured to be attained for threshold graphs. We prove the conjecture to hold for graphs with the property that for each k there is a threshold graph on the same number of nodes and edges whose sum of the k largest Laplacian eigenvalues exceeds that of the k largest Laplacian eigenvalues of the graph. We call such graphs spectrally threshold dominated. These graphs include split graphs and cographs and spectral threshold dominance is preserved by disjoint unions and taking complements. We conjecture that all graphs are spectrally threshold dominated. This conjecture turns out to be equivalent to Brouwer's conjecture concerning a bound on the sum of the k largest Laplacian eigenvalues.
|
2 |
Spectral threshold dominance, Brouwer's conjecture and maximality of Laplacian energyHelmberg, Christoph, Trevisan, Vilmar 11 June 2015 (has links)
The Laplacian energy of a graph is the sum of the distances of the eigenvalues of the Laplacian matrix of the graph to the graph's average degree. The maximum Laplacian energy over all graphs on n nodes and m edges is conjectured to be attained for threshold graphs. We prove the conjecture to hold for graphs with the property that for each k there is a threshold graph on the same number of nodes and edges whose sum of the k largest Laplacian eigenvalues exceeds that of the k largest Laplacian eigenvalues of the graph. We call such graphs spectrally threshold dominated. These graphs include split graphs and cographs and spectral threshold dominance is preserved by disjoint unions and taking complements. We conjecture that all graphs are spectrally threshold dominated. This conjecture turns out to be equivalent to Brouwer's conjecture concerning a bound on the sum of the k largest Laplacian eigenvalues.
|
3 |
Алгоритмы построения максимальных графических разбиений, доминирующих заданное графическое разбиение : магистерская диссертация / Algorithms for constructing maximal graphical partitions that dominate a given graphical partitionЗуев, В. В., Zuev, V. V. January 2023 (has links)
В работе рассмотрены разбиения целых неотрицательных чисел и изучены некоторые детали строения решеток разбиений. Решетка разбиений задается отношением доминирования, которое определяется как покомпонентное доминирование соответственных частичных сумм разбиений. Особое внимание уделено графическим разбиениям. Графическим называется разбиение, которые составлено из степеней вершин графа с добавлением нулей. Проведено исследование множества максимальных графических разбиений, доминирующих заданное графическое разбиение. Для исследования написана компьютерная программа на языке Python, позволяющая проверять гипотезы для разбиений небольших чисел. Основной результат работы – алгоритм построения всех максимальных графических разбиений, доминирующих заданное разбиение и имеющих такой же вес. Этот алгоритм базируется на основной теореме, которая описывает точное строение множества таких максимальных графических разбиений. Приведена программная реализация найденного алгоритма. / The work examines partitions of non-negative integers and studies some details of the structure of partition lattices. The lattice of partitions is given by a dominance relation, which is defined as the component-wise dominance of the corresponding partial sums of partitions. Particular attention is paid to graphical divisions. A graphical partition is a partition that is composed of the degrees of the vertices of the graph with the addition of zeros. A study of the set of maximal graphical partitions that dominate a given graphical partition has been carried out. For the study, a computer program was written in Python, which allows testing hypotheses for partitions of small numbers. The main result of the work is an algorithm for constructing all maximal graphical partitions that dominate a given partition and have the same weight. This algorithm is based on a fundamental theorem that describes the exact structure of the set of such maximal graphical partitions. A software implementation of the found algorithm is given.
|
Page generated in 0.013 seconds