{
  "id": "1302.1687",
  "version": "v1",
  "published": "2013-02-07T10:07:06.000Z",
  "updated": "2013-02-07T10:07:06.000Z",
  "title": "A Turán-type problem on degree sequence",
  "authors": [
    "Xueliang Li",
    "Yongtang Shi"
  ],
  "comment": "9 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given $p\\geq 0$ and a graph $G$ whose degree sequence is $d_1,d_2,\\ldots,d_n$, let $e_p(G)=\\sum_{i=1}^n d_i^p$. Caro and Yuster introduced a Tur\\'an-type problem for $e_p(G)$: given $p\\geq 0$, how large can $e_p(G)$ be if $G$ has no subgraph of a particular type. Denote by $ex_p(n,H)$ the maximum value of $e_p(G)$ taken over all graphs with $n$ vertices that do not contain $H$ as a subgraph. Clearly, $ex_1(n,H)=2ex(n,H)$, where $ex(n,H)$ denotes the classical Tur\\'an number, i.e., the maximum number of edges among all $H$-free graphs with $n$ vertices. Pikhurko and Taraz generalize this Tur\\'an-type problem: let $f$ be a non-negative increasing real function and $e_f(G)=\\sum_{i=1}^n f(d_i)$, and then define $ex_f(n,H)$ as the maximum value of $e_f(G)$ taken over all graphs with $n$ vertices that do not contain $H$ as a subgraph. Observe that $ex_f(n,H)=ex(n,H)$ if $f(x)=x/2$, $ex_f(n,H)=ex_p(n,H)$ if $f(x)=x^p$. Bollob\\'as and Nikiforov mentioned that it is important to study concrete functions. They gave an example $f(x)=\\phi(k)={x\\choose k}$, since $\\sum_{i=1}^n{d_i\\choose k}$ counts the $(k+1)$-vertex subgraphs of $G$ with a dominating vertex. Denote by $T_r(n)$ the $r$-partite Tur\\'an graph of order $n$. In this paper, using the Bollob\\'as--Nikiforov's methods, we give some results on $ex_{\\phi}(n,K_{r+1})$ $(r\\geq 2)$ as follows: for $k=1,2$, $ex_\\phi(n,K_{r+1})=e_\\phi(T_r(n))$; for each $k$, there exists a constant $c=c(k)$ such that for every $r\\geq c(k)$ and sufficiently large $n$, $ex_\\phi(n,K_{r+1})=e_\\phi(T_r(n))$; for a fixed $(r+1)$-chromatic graph $H$ and every $k$, when $n$ is sufficiently large, we have $ex_\\phi(n,H)=e_\\phi(n,K_{r+1})+o(n^{k+1})$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-02-07T10:07:06.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C07"
    ],
    "keywords": [
      "degree sequence",
      "turán-type problem",
      "maximum value",
      "turan-type problem",
      "sufficiently large"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1302.1687L"
    }
  }
}