2
$\begingroup$

I have come across a graph-theoretic problem where it would be nice to bound the "sum of squared degrees", in the following sense. We have a graph $G$ with vertex set $[n]$ and let $d(G) = \sum_{i=1}^n \deg(i)^2$.

Has this parameter been studied before, perhaps in some special cases? I would appreciate any pointers to the literature, especially for cases in which the order of $d(G)$ is significantly less than $n^3$. In particular, is this true when $G$ is tripartite and the edge set of $G$ is a union of disjoint triangles?

Edit. Based on the comments below, it seems that the problem reduces to the following. Suppose that a graph $G$ is such that its edge set is a union of triangles (no two triangles share an edge but they may share a vertex). Can one bound the number of cherries (ordered triples $(u,v,w)$ such that $v$ is adjacent to both $u$ and $w$), possibly by $O(n^2)$? I apologise if this is somewhat trivial, I cannot see the argument straightaway.

Edit 2. This should really go in a comment to the answer by Seva, but I cannot figure out how to attach an image. I believe this is a counterexample, as the edge set is the union of four edge-disjoint triangles, but vertices $0$ and $3$ are the endvertices of two distinct cherries.

enter image description here

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ The sum of squares of the degrees is, essentially, the number of "cherries" (triples of vertices $(u,v,w)$ with $v$ adjacent to both $u$ and $w$). The rest depends on exactly what do you want to prove. $\endgroup$
    – Seva
    Commented Sep 25, 2021 at 17:42
  • 1
    $\begingroup$ @Seva In the case where the edge set is a union of disjoint triangles, the number of cherries is exactly the number of edges. Does this mean that $d(G)$ is roughly the number of edges? $\endgroup$
    – Marcel K. Goh
    Commented Sep 25, 2021 at 17:57
  • 2
    $\begingroup$ In this count, every triple $(u,v,w)$ gives raise to two cherries. (That is, the cherries are oriented.) If we let $M$ denote the number of nonoriented cherries, then the sum of the squares is $2M+2e$, which for a union of triangles gives $4e$ for the sum of the squares. $\endgroup$
    – Seva
    Commented Sep 25, 2021 at 18:15
  • 2
    $\begingroup$ @Seva Thanks for this calculation! It is quite surprising to me that the sum of the squares is on the same order as the number of edges in my tripartite graph because it raises an apparent contradiction. I will work it out precisely to see what is going on. $\endgroup$
    – Marcel K. Goh
    Commented Sep 25, 2021 at 18:18
  • 2
    $\begingroup$ Your sum is $o(n^3)$, and you cannot do better than, say, $n^3e^{-c\sqrt{\ln n}}$; google for the "diamond-free lemma". $\endgroup$
    – Seva
    Commented Sep 26, 2021 at 6:32

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .