Egan and Nikolayevsky's conjecture on degree sequences of triangular simple graphs

From papers

Let n3n\geq 3 and let (d1,,dn)(d_1,\ldots,d_n) be a sequence of integers satisfying

d1dn4,d_1\geq\cdots\geq d_n\geq 4, d1++dn is even,d_1+\cdots+d_n\text{ is even},

and

i=1kdik(k1)+i=k+1nmin{di,k}for every k[n].\sum_{i=1}^k d_i\leq k(k-1)+\sum_{i=k+1}^n\min\{d_i,k\}\quad\text{for every }k\in[n].

Here a triangular simple graph is a simple graph in which every edge is contained in a triangle. Egan and Nikolayevsky's conjecture. The sequence (d1,,dn)(d_1,\ldots,d_n) is the degree sequence of a triangular simple graph. This is the simple-graph degree-sequence conjecture that motivates the multigraph analogue studied in the paper; the cited authors proved it in some special cases, but the general assertion is not resolved in the supplied text.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

John Talbot and Jun Yan, “Degree sequences of triangular multigraphs”, arXiv:2311.00110 (2023).

Solutions 0

No solutions have been posted yet.