|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A Tur'an-type problem on degree sequence | | Xueliang Li
; Yongtang Shi
; | | Date: |
7 Feb 2013 | | Abstract: | Given $pgeq 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 $pgeq 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)={xchoose k}$, since $sum_{i=1}^n{d_ichoose 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})$ $(rgeq 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 $rgeq 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})$. | | Source: | arXiv, 1302.1687 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER