{
  "id": "2312.07005",
  "version": "v1",
  "published": "2023-12-12T06:29:43.000Z",
  "updated": "2023-12-12T06:29:43.000Z",
  "title": "Extremal results on degree powers in some classes of graphs",
  "authors": [
    "Yufei Chang",
    "Xiaodan Chen",
    "Shuting Zhang"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a simple graph of order $n$ with degree sequence $(d_1,d_2,\\cdots,d_n)$. For an integer $p>1$, let $e_p(G)=\\sum_{i=1}^n d^{p}_i$ and let $ex_p(n,H)$ be the maximum value of $e_p(G)$ among all graphs with $n$ vertices that do not contain $H$ as a subgraph (known as $H$-free graphs). Caro and Yuster proposed the problem of determining the exact value of $ex_2(n,C_4)$, where $C_4$ is the cycle of length $4$. In this paper, we show that if $G$ is a $C_4$-free graph having $n\\geq 4$ vertices and $m\\leq \\lfloor 3(n-1)/2\\rfloor$ edges and no isolated vertices, then $e_p(G)\\leq e_p(F_n)$, with equality if and only if $G$ is the friendship graph $F_n$. This yields that for $n\\geq 4$, $ex_p(n,\\mathcal{C}^*)=e_p(F_n)$ and $F_n$ is the unique extremal graph, which is an improved complement of Caro and Yuster's result on $ex_p(n,\\mathcal{C}^*)$, where $\\mathcal{C}^*$ denotes the family of cycles of even lengths. We also determine the maximum value of $e_p(\\cdot)$ among all minimally $t$-(edge)-connected graphs with small $t$ or among all $k$-degenerate graphs, and characterize the corresponding extremal graphs. A key tool in our approach is majorization.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-12-12T06:29:43.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "degree powers",
      "extremal results",
      "free graph",
      "maximum value",
      "unique extremal graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}