2018/07/02 by De-Yan Zeng, Zeng, De-Yan, Dong-Yang Zhai +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1807.00470
openalex publication_date 2018/07/02 · openalex created_date 2018/07/10 · openalex updated_date 2026/07/28
A simple graph G is an \it 2-tree if G=K3, or G has a vertex v of degree 2, whose neighbors are adjacent, and G-v is an 2-tree. Clearly, if G is an 2-tree on n vertices, then |E(G)|=2n-3. A non-increasing sequence π=(d1,…,dn) of nonnegative integers is a \it 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≥ 2, n≥ (9)/(2)k2+(19)/(2)k and π=(d1,…,dn) is a graphic sequence with ∑i=1n di>(k-2)n, then π has a realization containing every 1-tree (the usual tree) on k vertices. Moreover, the lower bound (k-2)n is the best possible. This is a variation of a conjecture due to Erdős and Sós. In this paper, we investigate an analogue problem for 2-trees and prove that if k≥ 3 is an integer with k≡ i(mod 3), n≥20\lfloor(k)/(3)\rfloor2+31\lfloor(k)/(3)\rfloor+12 and π=(d1,…,dn) is a graphic sequence with ∑i=1n di>max\(k-1)(n-1),2\lfloor(2k)/(3)\rfloor n-2n-\lfloor(2k)/(3)\rfloor2+\lfloor(2k)/(3)\rfloor+1-(-1)i\, then π has a realization containing every 2-tree on k vertices. Moreover, the lower bound max\(k-1)(n-1),2\lfloor(2k)/(3)\rfloor n-2n-\lfloor(2k)/(3)\rfloor2+\lfloor(2k)/(3)\rfloor+1-(-1)i\ is the best possible. This result implies a conjecture due to Zeng and Yin (Discrete Math. Theor. Comput. Sci., 17(3)(2016), 315--326).