Opuscula Math. 37, no. 4 (2017), 617-639

Opuscula Mathematica

Fan's condition on induced subgraphs for circumference and pancyclicity

Wojciech Wideł

Abstract. Let \(\mathcal{H}\) be a family of simple graphs and \(k\) be a positive integer. We say that a graph \(G\) of order \(n\geq k\) satisfies Fan's condition with respect to \(\mathcal{H}\) with constant \(k\), if for every induced subgraph \(H\) of \(G\) isomorphic to any of the graphs from \(\mathcal{H}\) the following holds: \[\forall u,v\in V(H)\colon d_H(u,v)=2\,\Rightarrow \max\{d_G(u),d_G(v)\}\geq k/2.\] If \(G\) satisfies the above condition, we write \(G\in\mathcal{F}(\mathcal{H},k)\). In this paper we show that if \(G\) is \(2\)-connected and \(G\in\mathcal{F}(\{K_{1,3},P_4\},k)\), then \(G\) contains a cycle of length at least \(k\), and that if \(G\in\mathcal{F}(\{K_{1,3},P_4\},n)\), then \(G\) is pancyclic with some exceptions. As corollaries we obtain the previous results by Fan, Benhocine and Wojda, and Ning.

Keywords: Fan's condition, circumference, hamiltonian cycle, pancyclicity.

Mathematics Subject Classification: 05C38, 05C45.

Full text (pdf)

  • Wojciech Wideł
  • AGH University of Science and Technology, Faculty of Applied Mathematics, al. A. Mickiewicza 30, 30-059 Krakow, Poland
  • Communicated by Ingo Schiermeyer.
  • Received: 2016-07-03.
  • Revised: 2016-11-23.
  • Accepted: 2016-11-23.
  • Published online: 2017-04-28.
Opuscula Mathematica - cover

Cite this article as:
Wojciech Wideł, Fan's condition on induced subgraphs for circumference and pancyclicity, Opuscula Math. 37, no. 4 (2017), 617-639, http://dx.doi.org/10.7494/OpMath.2017.37.4.617

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.