8
$\begingroup$

For a simple graph $G$ on $n$ vertices, let us define

$$\mathcal{I}_{n}(G)=\sum_{i,j=1}^{n}|\deg\ x_{i}-\deg\ x_{j}|^{3}.$$

I know that there are many different topological indices defined and studied for graphs. Have You ever seen such that was defined similar as above? Can You provide any references?

I am highly interested in finding $\sup \mathcal{I}_{n}$ over all graphs with $n$ vertices (or at least some tight upper bound). What I have tried myself, was noticing that $\mathcal{I}_{n}$ must be maximized by a threshold graph - these graphs produce degree sequences that are extreme points of he convex hull of all degree sequences. But this didn't lead me too far. I will be glad for any insight.

Improve this question
$\endgroup$
7
  • $\begingroup$ Is it obvious that this number is always divisible by four - for any value of 3? $\endgroup$
    – Martin Rubey
    Commented Feb 29, 2020 at 15:36
  • 2
    $\begingroup$ The "Albertson index" is a bit similar, see findstat.org/St001350 $\endgroup$
    – Martin Rubey
    Commented Feb 29, 2020 at 15:41
  • 2
    $\begingroup$ actually, dmtcs.episciences.org/1263 considers your invariant with $3:=1$, which might be helpful. $\endgroup$
    – Martin Rubey
    Commented Feb 29, 2020 at 15:46
  • 1
    $\begingroup$ Divisibility by $4$ is easy (but tedious) to show by induction on the number of edges. $\endgroup$
    – Martin Rubey
    Commented Feb 29, 2020 at 16:58
  • 2
    $\begingroup$ This index $\mathcal{I_{n}}$ is a convex function of degree sequence $\mathcal {deg}x_{1},...,\mathcal{deg}x_{n}$. Call the set of all such graphic sequences $D$. Then we can look on $D^{*}=\mathcal{Con}D$ - a convex hull of $D$. $I_{n}$ must then attain it's maximum on some extreme point of $D^{*}$. It can be shown, that such extreme points of $D^{*}$ are exactly those corresponding to threshold graphs. $\endgroup$
    – user153000
    Commented Mar 4, 2020 at 19:47

1 Answer 1

Reset to default
4
+150
$\begingroup$

I will guess that the optimum occurs for $k$ isolated vertices and a complete graph on the other $n-k$ where $k=\lfloor\frac{n+1}5\rfloor.$ The same count occurs for $k$ vertices of degree $n-1$ and no other edges so the other $n-k$ have degree $k.$

Past that I have these observations:

  • A graph $G$ and the complement $\bar G$ give the same value to the sum.
  • If the maximum degree in an optimal $G$ is $\Delta$ then any degree $\Delta$ vertex is connected to any other. This is because connecting two such increases some of the $|\deg(x_i)-\deg(x_j)|$ but decreases none.
  • Similarly two vertices with the minimum degree are non-adjacent.
  • For the type of graph I defined above, the count is $k(n-k)(n-k-1)^3.$ The maximum over the reals occurs at $$k=\frac{3\,n-\sqrt {4\,{n}^{2}-n+1}-1}5\approx \frac{n}{5}-\frac3{20}.$$

As commented, the exponent of $3$ is relevant. Take the conjectured optimal case of a $K_{4t}$ and $t$ isolated vertices. Deleting one edge reduces $2t$ degree difference from $4t-1$ to $4t-2$ and increases $2(4t-2)$ other differences from $0$ to $1.$ If one is summing the square or cubes of the differences that is worse. But with exponent $1$ that is an improvement.

NOTE Based on limited calculations, The same things seem maximal if we replace the exponent of 3 by 2

Improve this answer
$\endgroup$
5
  • $\begingroup$ I agree, in my opinion this should be a maximizer. But it must somehow depend on power $3$. For $1$ instead of $3$ we get so called "total irregularity index" and maximizer turns out to be different... $\endgroup$
    – user153000
    Commented Mar 1, 2020 at 18:01
  • 2
    $\begingroup$ This conjecture is correct up to 13 vertices. If the focus on threshold graphs is solid, using the representation of a threshold graph as a binary string (0 for add an isolated vertex, 1 for add a new vertex joined to everything so far) might be the way to go. I think that the effect of changing 01 to 10 in the string is simple. But I stopped working on it so feel free ;). $\endgroup$
    – Brendan McKay
    Commented Mar 1, 2020 at 23:04
  • $\begingroup$ I don't think that last remark - changing $01$ with $10$ - is true. I have been checking best binary sequences with fixed number of ones and the maximisers are not always $111...000$ or $000...111$. $\endgroup$
    – user153000
    Commented Mar 1, 2020 at 23:20
  • $\begingroup$ @StanTuwim That's interesting. Do you find examples that beat Aaron's records? $\endgroup$
    – Brendan McKay
    Commented Mar 1, 2020 at 23:49
  • $\begingroup$ Luckily, I have not. $\endgroup$
    – user153000
    Commented Mar 2, 2020 at 8:37

You must log in to answer this question.