๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

(n,e)-Graphs with maximum sum of squares of degrees*

โœ Scribed by Peled, Uri N.; Petreschi, Rossella; Sterbini, Andrea

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
308 KB
Volume
31
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

โœฆ Synopsis

Among all simple graphs on n vertices and e edges, which ones have the largest sum of squares of the vertex degrees? It is easy to see that they must be threshold graphs, but not every threshold graph is optimal in this sense. Boesch et al. [Boesch et al., Tech Rep, Stevens Inst Tech, Hoboken NJ, 1990] showed that for given n and e there exists exactly one graph of the form G 1 (p, q, r) = K p + (S q โˆช K 1,r ) and exactly one G 2 (p, q, r) = S p โˆช (K q + K 1,r ) and that one of them is optimal, where K and S indicate complete and edgeless graphs, K 1,r indicates a star on r + 1 vertices, โˆช indicates disjoint union, and + indicates complete disjoint join. We specify a general threshold graph in the form G * 1 (a, b, c, d, . . .

๐Ÿ“œ SIMILAR VOLUMES

Total colorings of planar graphs with la
Total colorings of planar graphs with large maximum degree
โœ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 97 KB ๐Ÿ‘ 2 views

It is proved that a planar graph with maximum degree โˆ† โ‰ฅ 11 has total (vertex-edge) chromatic number โˆ† + 1.

Constructing a bipartite graph of maximu
Constructing a bipartite graph of maximum connectivity with prescribed degrees
โœ Asano, Takao ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 328 KB ๐Ÿ‘ 2 views

d 2,n 2 ) is a bipartite graphical sequence, if there is a bipartite graph G with degrees {D 1 , D 2 } (i.e., G has two independent vertex sets In other words, {D 1 , D 2 } is a bipartite graphical sequence if and only if there is an n 1 1 n 2 matrix of 0's and 1's having d 1j 1 1's in row j 1 and