On a problem of potentially pancyclic-graphic sequences due to S.B. Rao (Q2316313)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a problem of potentially pancyclic-graphic sequences due to S.B. Rao |
scientific article |
Statements
On a problem of potentially pancyclic-graphic sequences due to S.B. Rao (English)
0 references
26 July 2019
0 references
A non-increasing sequence $\pi =(d_1,d_2,\dots,d_n)$ of nonnegative integers is said to be graphic if it is the degree sequence of a simple graph $G$ on $n$ vertices, and such a graph $G$ is called a realization of $\pi$. A graphic sequence $\pi$ is said to be potentially Hamiltonian-graphic if there is a realization of $\pi$ containing a Hamiltonian cycle, and it is called potentially pancyclic-graphic if there is a realization of $\pi$ containing cycles of every length from 3 to $n$. Moreover, we say $\pi$ to near regular graphic if $d_1-d_n\leq 1$. \textit{A. R. Rao} and \textit{S. B. Rao} [J. Comb. Theory, Ser. B 13, 185--191 (1972; Zbl 0224.05126)] and \textit{S. Kundu} [Discrete Math. 6, 367--376 (1973; Zbl 0278.05115)] presented a characterization of $\pi$ that is potentially Hamiltonian-graphic. \textit{S. B. Rao} [Lect. Notes Math. 885, 417--440 (1981; Zbl 0474.05043), Unsolved Problem 2] further posed the following problem: present a characterization of $\pi =(d_1,d_2,\dots,d_n)$ that is potentially pancyclic-graphic. In this paper, the authors solve this problem and present the following results: \par (i) When $4\leq n\leq 11$, $\pi$ is potentially pancyclic-graphic if it is potentially Hamiltonian-graphic (under imposed conditions on $d_i^{\prime}s$). \par (ii) For $d_{n}\geq 3$, $\pi$ is potentially pancyclic-graphic if $\pi$ is near regular graphic. Along with following two conjectures: \par Conjecture 1. If $\pi =(d_1,d_2,\dots,d_n)$ is a potentially Hamiltonian-graphic sequence with $d_1\geq \left\lfloor \frac{n}{2}\right\rfloor +2$, then $\pi$ is potentially pancyclic-graphic. \par Conjecture 2. If $\pi =(d_1,d_2,\dots,d_n)$ is a potentially Hamiltonian-graphic sequence with $d_n\geq 3$, then $\pi$ is potentially pancyclic-graphic.
0 references
graphic sequence
0 references
potentially Hamiltonian-graphic sequence
0 references
potentially pancyclic-graphic sequence
0 references