An extremal problem for a graphic sequence to have a realization containing every 2-tree with prescribed size
An extremal problem for a graphic sequence to have a realization containing every 2-tree with prescribed size
复制标题
图形序列的一个极值问题，其实现包含每个具有规定大小的二叉树
DOI：
10.46298/dmtcs.2152
复制
发表时间：
2016-08
影响因子：
0.7
通讯作者：
尹建华
中科院分区：
文献类型：
--
作者：
曾德炎;尹建华
A graph $G$ is a $2$ -tree if $G=K_3$, or $G$ has a vertex $v$ of degree 2, whose neighbors are adjacent, and $G-v$ is a 2-tree. Clearly, if $G$ is a 2-tree on $n$ vertices, then $|E(G)|=2n-3$. A non-increasing sequence $\pi =(d_1, \ldots ,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. Yin and Li (Acta Mathematica Sinica, English Series, 25(2009)795–802) proved that if $k \geq 2$, $n \geq \frac{9}{2}k^2 + \frac{19}{2}k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > (k-2)n$, then $\pi$ has a realization containing every tree on $k$ vertices as a subgraph. Moreover, the lower bound $(k-2)n$ is the best possible. This is a variation of a conjecture due to Erdős and Sos. In this paper, we investigate an analogue extremal problem for 2-trees and prove that if $k \geq 3$, $n \geq 2k^2-k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > \frac{4kn}{3} - \frac{5n}{3}$ then $\pi$ has a realization containing every 2-tree on $k$ vertices as a subgraph. We also show that the lower bound $\frac{4kn}{3} - \frac{5n}{3}$ is almost the best possible.
A graph $G$ is a $2$ -tree if $G=K_3$, or $G$ has a vertex $v$ of degree 2, whose neighbors are adjacent, and $G-v$ is a 2-tree. Clearly, if $G$ is a 2-tree on $n$ vertices, then $|E(G)|=2n-3$. A non-increasing sequence $\pi =(d_1, \ldots ,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. Yin and Li (Acta Mathematica Sinica, English Series, 25(2009)795–802) proved that if $k \geq 2$, $n \geq \frac{9}{2}k^2 + \frac{19}{2}k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > (k-2)n$, then $\pi$ has a realization containing every tree on $k$ vertices as a subgraph. Moreover, the lower bound $(k-2)n$ is the best possible. This is a variation of a conjecture due to Erdős and Sos. In this paper, we investigate an analogue extremal problem for 2-trees and prove that if $k \geq 3$, $n \geq 2k^2-k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > \frac{4kn}{3} - \frac{5n}{3}$ then $\pi$ has a realization containing every 2-tree on $k$ vertices as a subgraph. We also show that the lower bound $\frac{4kn}{3} - \frac{5n}{3}$ is almost the best possible.
登录
查看更多内容
影响因子：
0.9
作者：
P. Bose;V. Dujmovic;D. Krizanc;S. Langerman;Pat Morin;D. Wood;Stefanie Wuhrer
通讯作者：
P. Bose;V. Dujmovic;D. Krizanc;S. Langerman;Pat Morin;D. Wood;Stefanie Wuhrer
DOI：
10.1057/jors.1977.45
发表时间：
1978-03
期刊：
--
影响因子：
--
作者：
E. Lloyd;J. Bondy;U. Murty
通讯作者：
E. Lloyd;J. Bondy;U. Murty
DOI：
10.1007/s10114-009-7260-2
发表时间：
2009-04
期刊：
Acta Mathematica Sinica, English Series
影响因子：
--
作者：
Jianhua Yin;Jiongsheng Li
通讯作者：
Jianhua Yin;Jiongsheng Li
DOI：
10.1016/s0166-218x(96)00045-5
发表时间：
1997-05
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
L. Cai
通讯作者：
L. Cai
DOI：
10.1016/s0012-365x(02)00765-3
发表时间：
2003-01
期刊：
Discret. Math.
影响因子：
--
作者：
Jianhua Yin;Jiongsheng Li
通讯作者：
Jianhua Yin;Jiongsheng Li