De-Yan Zeng ; Jian-Hua Yin - An extremal problem for a graphic sequence to have a realization containing every 2-tree with prescribed size

dmtcs:2152 - Discrete Mathematics & Theoretical Computer Science, August 6, 2016, Vol. 17 no. 3 - https://doi.org/10.46298/dmtcs.2152
An extremal problem for a graphic sequence to have a realization containing every 2-tree with prescribed sizeArticle

Authors: De-Yan Zeng 1,2; Jian-Hua Yin 1

  • 1 Department of Mathematics, College of Information Science and Technology [Haikou]
  • 2 Institute of Technology, Sanya University

A graph $G$ is a $2$<i>-tree</i> 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 <i>graphic sequence</i> if it is realizable by a simple graph $G$ on $n$ vertices. Yin and Li (Acta Mathematica Sinica, English Series, 25(2009)795&#x2013;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&#x0151;s and S&oacute;s. 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.


Volume: Vol. 17 no. 3
Section: Graph Theory
Published on: August 6, 2016
Submitted on: March 23, 2015
Keywords: 2-trees., graphic sequences, realization,degree sequences,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 416 times.
This article's PDF has been downloaded 578 times.