A non-increasing sequence π = (d1, ⋯, dn) of nonnegative integers is said to be a graphic sequence if it is realizable by a simple graph G on n vertices. In this case, G is referred to as a realization of π. In terms of graphic sequences, the Loebl-Komlós-Sós conjecture states that for any integers k and n, if π = (d1, ⋯, dn) is a graphic sequence with <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2024_1055_Article_IEq1.gif" Format="GIF" Height="25" Rendition="HTML" Resolution="72" Type="Linedraw" Width="69" /> </InlineMediaObject> <EquationSource Format="TEX">${d_{\left\lceil {{n \over 2}} \right\rceil}} \ge k$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <msub> <mi>d</mi> <mrow> <mrow> <mo>⌈</mo> <mrow> <mrow> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> </mrow> </mrow> <mo>⌉</mo> </mrow> </mrow> </msub> </mrow> <mo>≥</mo> <mi>k</mi> </math></EquationSource> </InlineEquation>, then every realization of π contains all trees with k edges as subgraphs. This problem can be viewed as a forcible degree sequence problem. In this paper, we consider a potential degree sequence problem of the Loebl-Komlós-Sós conjecture, that is, we prove that for any integers k and n, if π = {d1, ⋯, dn) is a graphic sequence with <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2024_1055_Article_IEq1.gif" Format="GIF" Height="25" Rendition="HTML" Resolution="72" Type="Linedraw" Width="69" /> </InlineMediaObject> <EquationSource Format="TEX">${d_{\left\lceil {{n \over 2}} \right\rceil}} \ge k$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <msub> <mi>d</mi> <mrow> <mrow> <mo>⌈</mo> <mrow> <mrow> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> </mrow> </mrow> <mo>⌉</mo> </mrow> </mrow> </msub> </mrow> <mo>≥</mo> <mi>k</mi> </math></EquationSource> </InlineEquation>, then there is a realization of π containing all trees with k edges as subgraphs.

A Potential Degree Sequence Problem of the Loebl-Komlós-Sós Conjecture

期刊论文
发表日期：

2025年10月6日

查看全文

Guang-ming Li,
Jian-hua Yin

摘要

A non-increasing sequence π = (d₁, ⋯, d_n) of nonnegative integers is said to be a graphic sequence if it is realizable by a simple graph G on n vertices. In this case, G is referred to as a realization of π. In terms of graphic sequences, the Loebl-Komlós-Sós conjecture states that for any integers k and n, if π = (d₁, ⋯, d_n) is a graphic sequence with ${d_{\left\lceil {{n \over 2}} \right\rceil}} \ge k$ $d_{⌈ \frac{n}{2} ⌉} \geq k$ , then every realization of π contains all trees with k edges as subgraphs. This problem can be viewed as a forcible degree sequence problem. In this paper, we consider a potential degree sequence problem of the Loebl-Komlós-Sós conjecture, that is, we prove that for any integers k and n, if π = {d₁, ⋯, d_n) is a graphic sequence with ${d_{\left\lceil {{n \over 2}} \right\rceil}} \ge k$ $d_{⌈ \frac{n}{2} ⌉} \geq k$ , then there is a realization of π containing all trees with k edges as subgraphs.