A P\'{o}sa-type condition of potentially _3C_\ell-graphic sequences

arXiv1912.00309MaRDI QIDQ6330179FDOQ6330179

Publication date: 30 November 2019

Abstract: A non-increasing sequence

p i = (d_{1}, l d o t s, d_{n})

of nonnegative integers is said to be graphic if it is realizable by a simple graph

G

on

n

vertices. A graphic sequence

p i = (d_{1}, l d o t s, d_{n})

is said to be potentially

_{3} C_{e} l l

-graphic if there is a realization of

p i

containing cycles of every length

r

,

3 l e r l e e l l

. It is well-known that if the non-increasing degree sequence

(d_{1}, l d o t s, d_{e} l l)

of a graph

G

on

e l l

vertices satisfies the P'{o}sa condition that

d_{e l l + 1 - i} g e i + 1

for every

i

with

1 l e i < f r a c e l l 2

, then

G

is either pancyclic or bipartite. In this paper, we obtain a P'{o}sa-type condition of potentially

_{3} C_{e} l l

-graphic sequences, that is, we prove that if

e l l g e 5

is an integer,

n g e e l l

and

p i = (d_{1}, l d o t s, d_{n})

is a graphic sequence with

d_{e l l + 1 - i} g e i + 1

for every

i

with

1 l e i < f r a c e l l 2

, then

p i

is potentially

_{3} C_{e} l l

-graphic. This result improves a Dirac-type condition of potentially

_{3} C_{e} l l

-graphic sequences due to Yin et al. [Appl. Math. Comput., 353 (2019) 88--94], and asymptotically answers a problem due to Li et al. [Adv. Math., 33 (2004) 273--283]. As an application, this result also completely implies the value

s i g m a (C_{e} l l, n)

for

e l l g e 5

and

n g e e l l

, improving the result of Lai [J. Combin. Math. Combin. Comput., 49 (2004) 57--64].

This page was built for publication: A P\'{o}sa-type condition of potentially $_3C_\ell$-graphic sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330179)