Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.06552 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913193596551168 |
|---|---|
| author | Apollonio, Nicola |
| author_facet | Apollonio, Nicola |
| contents | We show that for a certain class of convex functions $f$, including the exponential functions $x\mapsto e^{λx}$ with $λ>0$ a real number, and all the powers $x\mapsto x^β$, $x\geq 0$ and $β\geq 2$ a real number, with a unique small exception, if $(d_1,\ldots,d_n)$ ranges over the degree sequences of graphs with $n$ vertices and $m$ edges and $m\leq n-1$, then the maximum of $\sum_i f(d_i)$ is uniquely attained by the degree sequence of a quasi-star graph, namely, a graph consisting of a star plus possibly additional isolated vertices. This result significantly extends a similar result in [D.~Ismailescu, D.~Stefanica, Minimizer graphs for a class of extremal problems, J.~Graph Theory,~39~(4)~(2002)]. Dually, we show that for a certain class of concave functions $g$, including the negative exponential functions $x\mapsto 1-e^{-λx}$ with $λ>\ln(2)$ a real number, all the powers $x\mapsto x^α$, $x\geq 0$ and $0<α\leq \frac{1}{2}$ a real number, and the function $x\mapsto \frac{x}{x+1}$ for $x\geq 0$, if $(d_1,\ldots,d_n)$ ranges over the degree sequences of graphs with $n$ vertices and $m$ edges, then the minimum of $\sum_i g(d_i)$ is uniquely attained by the degree sequence of a quasi-complete graph, i.e., a graph consisting of a complete graph plus possibly an additional vertex connected to some but not all vertices of the complete graph, plus possibly isolated vertices. This result extends a similar result in the same paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_06552 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Functions that are uniquely maximized by sparse quasi-star graphs, and uniquely minimized by quasi-complete graphs Apollonio, Nicola Combinatorics We show that for a certain class of convex functions $f$, including the exponential functions $x\mapsto e^{λx}$ with $λ>0$ a real number, and all the powers $x\mapsto x^β$, $x\geq 0$ and $β\geq 2$ a real number, with a unique small exception, if $(d_1,\ldots,d_n)$ ranges over the degree sequences of graphs with $n$ vertices and $m$ edges and $m\leq n-1$, then the maximum of $\sum_i f(d_i)$ is uniquely attained by the degree sequence of a quasi-star graph, namely, a graph consisting of a star plus possibly additional isolated vertices. This result significantly extends a similar result in [D.~Ismailescu, D.~Stefanica, Minimizer graphs for a class of extremal problems, J.~Graph Theory,~39~(4)~(2002)]. Dually, we show that for a certain class of concave functions $g$, including the negative exponential functions $x\mapsto 1-e^{-λx}$ with $λ>\ln(2)$ a real number, all the powers $x\mapsto x^α$, $x\geq 0$ and $0<α\leq \frac{1}{2}$ a real number, and the function $x\mapsto \frac{x}{x+1}$ for $x\geq 0$, if $(d_1,\ldots,d_n)$ ranges over the degree sequences of graphs with $n$ vertices and $m$ edges, then the minimum of $\sum_i g(d_i)$ is uniquely attained by the degree sequence of a quasi-complete graph, i.e., a graph consisting of a complete graph plus possibly an additional vertex connected to some but not all vertices of the complete graph, plus possibly isolated vertices. This result extends a similar result in the same paper. |
| title | Functions that are uniquely maximized by sparse quasi-star graphs, and uniquely minimized by quasi-complete graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.06552 |