research career of a scholar to determine the scientific impact. To define
L-sequence, consider a scholar who has published $k$ articles in his/her
career. Let the first publication year be $y_{1}$ and the current year be
$y_{c}$. Then, the L-sequence of an author for $n^{th}$ year, denoted $L_{n}$,
is the h-index value computed on the basis of the citation counts of all the
publications received in the $n^{th}$ year. Thus, the L-sequence of the author
is $L_{y_{1}},L_{y_{1}+1},...............L_{y_{c}}$.

Apart from above indices, Bertoli-Barsotti and Lando, (2015) discussed the
mathematical model of h-index. Mathematical model of h-index for a scholar is
defined as:

$\displaystyle\tilde{h_{w}}=\tilde{h_{w}}(M,Cit,Cit_{max})=\left[\frac{W((\frac{M-1}{(1-\tilde{k}^{-1})}).log\frac{1}{(1-\tilde{k}^{-1})})}{log(1/(1-\tilde{k}^{-1}))}\right]$
(110)

where, $w$ indicates Lambert function and $\tilde{k}$ represents trimmed mean,
which is defined as:

$\tilde{k}=\frac{\tilde{Cit}}{(M-1)}$ (111)

Here, $M$ represents the total publication count and $\tilde{Cit}$ =
Cit-$cit_{max}$.

In this subsection, we have discussed all those indices which are a little bit
difficult to compute because of them being based on complex mathematical
models. Finally, we have concluded that in the field of scientometrics and
bibliometrics, several indices covers several things to asses the scientific
impact of scholars, but there is still an opportunity to improve the
evaluation process of the scientific impact of scholars. Several indices
complemented the h-index in the context of the total number of core items,
whereas several others cover the impact of co-authors in scientific
assessment. Apart from the core items and the number of co-authors, several
indices consider the excess citation count of core articles, some consider the
total number of cited articles, the total career of scholars, and more, to
enhance the scientific assessment of scholars. A huge number of indices use
mathematical expressions to share credit among co-authors, but simply the use
of mathematical formulas to express the contribution of scholars is not
justifiable. So, in this regard, there is scope for further research. Lastly,
only a limited number of articles have addressed the impact of excess citation
count.

Form the above study, we found that a limited number of research have been
conducted to account for the importance of excess citation count, tail-
articles citation count and the publications consistency. These all have a
significance in the scientific assessment of scholars. Our research is solely
based on the above mentioned issues. The summary of the index based on other
variants shown in the table 8.

Table 8: Summary of Index based other variants Index |  Definition |  Publication
---|---|---
|  Based on core-tail ratio |
$h^{2}$ upper-index |  $h^{2}upper=\frac{\sum_{k=1}^{h}(cit_{k}-h)}{\sum_{k=1}^{m}cit_{k}}\times 100$ |  Bornmann et al., (2010)
$h^{2}$ center-index |  $h^{2}center=\frac{h\times h}{\sum_{k=1}^{m}cit_{k}}\times 100$ |  Bornmann et al., (2010)
$h^{2}$ lower-index |  $h^{2}lower=\frac{\sum_{k=h+1}^{m}(cit_{k}-h)}{\sum_{k=1}^{m}cit_{k}}\times 100$ |  Bornmann et al., (2010)
$h^{{}^{\prime}}$-index |  $h^{{}^{\prime}}=Rh=\frac{eh}{t}$ Where R represents head-tail ratio by e and t-index. |  Zhang, (2013)
k-index |  $k=\frac{(cit_{all}/pub_{count})}{(cit_{T}/Cit_{H})}$ $cit_{all}$ is total citation count, $pub_{count}$ is total publication count, $cit_{T}$ total citation count of h-tail papers and $cit_{H}$ is the total citation count of h-core papers. |  Fred and Rousseau, (2010)
$k^{{}^{\prime}}$-index |  $k^{{}^{\prime}}=\frac{cit-pub}{Cit_{T}-cit_{H}}$ |  Chen et al., (2013)
Two sided h-index |  _The two sided h-index of a scholar for length $m$ is defined as: $h\pm m=(h_{-m},........,h_{-1},h_{0},h_{1},..........,h_{m})$ where $h_{0}$ represents the original h-index, the negative script represents the citations of the h-core articles with consecutive square up the top of the citation curve, and the positive script represents the citations of the h-tail articles with consecutive square out of the tail of citation curve._ |  García-Pérez, (2012)
|  Based on improvement of h-index to higher value |
Rational h-index ($h_{rat}$) |  _The rational h-index of an author is the h and the number of additional citation required to reach next h-index(h+1)_ , $h_{rat}=h+1-\frac{k}{2h+1}$, Where h is the h-index and k is the number of citation count required to reach h+1. The maximum number of citation required to reach next h-index is 2h+1. |  Ruane and Tol, (2008)
Real h-index |  $h_{r}=\frac{(h+1)cit_{h}-h.cit_{h+1}}{1-cit_{h+1}+cit_{h}}$ where, h is the h-index and $cit_{h}$ is the citation count of $h^{th}$ article. |  Guns and Rousseau, (2009)
Table 8: Summary of Index based other variants Continue.. Index |  Definition |  Publication
---|---|---
Stochastic h-index ($h_{s}$) |  $h_{s}=h+P$, where, $P$ is the probability of articles to become a part of h-core based on current publication to increase the index value to the next within a specific time period (e.g., within a year). |  Wu, (2010)
|  Based on variants of citation process |
ch-index |  _“The ch-index of a scholar is k if k of his/her articles have at least k citers each.”_ |  Isola and Wolfram, (2009)
f-index |  _“The f-index of a scholar is k if k of his/her articles have at least k coterminal citation each.”_ |  Katsaros et al., (2009)
Indirect h-index |  _“The indirect h-index of a scholar is m, if m of his/her articles have at least m single publication h-index each.”_ |  Egghe, 2011a
Average h-index |  _“The average h-index of a scholar is the average of the single publication h-index of h-core articles.”_ |  Egghe, 2011b
$h_{int}$-index |  _“The $h_{int}$-index of a scholar is k, if k of his/her articles have at least k number of international recognition each.”_ |  Kosmulski, 2010b
wl-index |  _“The wl-index of a scholar is the largest integer k, if k of his/her articles have at least k citation mentioned each.”_ |  Wan and Liu, (2014)
|  Miscellaneous indices |
$h_{\alpha}$-index |  _“The $h_{\alpha}$-index of a scholar is k, if k of his/her articles have at least $\alpha k$ citations each.”_ |  Van Eck and Waltman, (2008)
$\pi-index$ |  $\pi-index=0.01\times cit(A_{\pi})$, where, $cit(A_{\pi})$ is the citation count of an elite set of articles. |  Vinkler, (2009)
Citation speed index |  _“The citation speed index of a scholar is k, if k of his/her articles got first citation at least k months ago.”_ |  Bornmann and Daniel, (2010)
c-index |  $C_{\alpha}=max(min(\alpha k,Qt(p_{k}))):k\in\\{1,2,...,m\\}$ |  Domingo-Ferrera and Torrab, (2011)
Success index |  _The success index of an author sum of the success score of all article._ ($Success-index(A)=\sum_{k=1}^{m}SC_{k}$, where $SC_{k}$ is success score of $k^{th}$ publication.) |  Franceschini et al., (2012)
Summary citation index |  $SC=\sum_{p=1}^{m}\frac{\Phi(\phi_{p}IF_{p})}{A_{p}}+a\sum_{p=1}^{m}\frac{\Phi(IF_{p})}{A_{p}}$, |  Mikhailov, (2012)
$\tilde{h_{w}}$ |  $\tilde{h_{w}}=\tilde{h_{w}}(M,Cit,Cit_{max})=\left[\frac{W((\frac{M-1}{(1-\tilde{k}^{-1})}).log\frac{1}{(1-\tilde{k}^{-1})})}{log(1/(1-\tilde{k}^{-1}))}\right]$, Where w indicates Lambert function and $\tilde{k}$ represents trimmed mean. |  Bertoli-Barsotti and Lando, (2015)

##  3 Conclusions

In this article, we made an extensive literature review on h-index and its
alternative indices. In research community h-index plays an important role to
evaluate the scientific impact of individual, Institutions, college or
university to grant research project as well as a promotion or award. The
h-index got a lot of attention due to its simplicity.

Based on the characteristics of h-index and also to overcome the limitation of
h-index, several other indicators were proposed by eminent researchers. Some
of the variants extended the properties of h-index to overcome h-index big hit
problems, while some eminent researchers proposed other variants of h-index to
overcome the multi-authored problem. Many others indices were proposed to
overcome publication age problems, excess citation count problem, total
publication count problem. Some other variants that combine the advantages of
two indices to overcome shortcomings of other indices. Several other
indicators were proposed considers other parameters such as a number of citer,
number of citation mentioned, L-factor, number of success papers and so on.
Some of the researchers discussed the impact of self citation count and
proposed some other variants of h-index for account of self citation count.

Some other variants of h-index is based on the Pagerank algorithm to assign
influence of an article in the research community.

Here we found that all indices is categories in eight categories as Complement
of h-index, based on total number of author, publication age, Combination of
two indices, excess citation, total publication count, other variants and
account for self citation count.

In research community many other literatures discussed the h-index and its
alternatives theoretically & empirically and also discuss the advantages &
limitation of proposed variants.

## References

  * Abbas, (2011) Abbas, A. M. (2011).  Weighted indices for evaluating the quality of research with multiple authorship.  Scientometrics, 88(1):107–131.
  * Abbasi et al., (2010) Abbasi, A., Altmann, J., and Hwang, J. (2010).  Evaluating scholars based on their academic collaboration activities: two indices, the rc-index and the cc-index, for quantifying collaboration activities of researchers and scientific communities.  Scientometrics, 83(1):1–13.
  * Abbasi et al., (2009) Abbasi, A., Altmann, J., Hwang, J., et al. (2009).  Evaluating scholars based on their academic collaboration activities: The rc-index and cc-index for quantifying collaboration activities of researchers and scientific communities.  Technical report, Seoul National University; Technology Management, Economics, and Policy Program (TEMEP).
  * Abt, (2012) Abt, H. A. (2012).  A publication index that is independent of age.  Scientometrics, 91(3):863–868.
  * Ajiferuke and Wolfram, (2010) Ajiferuke, I. and Wolfram, D. (2010).  Citer analysis as a measure of research impact: Library and information science as a case study.  Scientometrics, 83(3):623–638.
  * Alonso et al., (2009) Alonso, S., Cabrerizo, F. J., Herrera-Viedma, E., and Herrera, F. (2009).  h-index: A review focused in its variants, computation and standardization for different scientific fields.  Journal of Informetrics, 3(4):273–289.
  * Alonso et al., (2010) Alonso, S., Cabrerizo, F. J., Herrera-Viedma, E., and Herrera, F. (2010).  hg-index: A new index to characterize the scientific output of researchers based on the h-and g-indices.  Scientometrics, 82(2):391–400.
  * Altmann et al., (2009) Altmann, J., Abbasi, A., and Hwang, J. (2009).  Evaluating the productivity of researchers and their communities: The rp-index and the cp-index.
  * Anderson et al., (2008) Anderson, T., Hankin, R., and Killworth, P. (2008).  Beyond the durfee square: Enhancing the h-index to score total publication output.  Scientometrics, 76(3):577–588.
  * Anne-Wil, (2010) Anne-Wil, H. (2010).  The publish or perish book: Your guide to effective and responsible citation analysis.  Melbourne, Australia: Tarma Software Research.
  * Aziz and Rozing, (2013) Aziz, N. A. and Rozing, M. P. (2013).  Profit (p)-index: the degree to which authors profit from co-authors.  PLoS One, 8(4):e59814.
  * Bar-Ilan, (2008) Bar-Ilan, J. (2008).  Informetrics at the beginning of the 21st century—a review.  Journal of informetrics, 2(1):1–52.
  * Batista et al., (2006) Batista, P. D., Campiteli, M. G., and Kinouchi, O. (2006).  Is it possible to compare researchers with different scientific interests?  Scientometrics, 68(1):179–189.
  * Bertoli-Barsotti and Lando, (2015) Bertoli-Barsotti, L. and Lando, T. (2015).  On a formula for the h-index.  Journal of Informetrics, 9(4):762–776.
  * Bihari and Tripathi, (2017) Bihari, A. and Tripathi, S. (2017).  Em-index: a new measure to evaluate the scientific impact of scientists.  Scientometrics, 112(1):659–677.
  * Bihari and Tripathi, (2018) Bihari, A. and Tripathi, S. (2018).  Year based em-index: a new approach to evaluate the scientific impact of scholars.  Scientometrics, pages 1–31.
  * Biswal, (2013) Biswal, A. K. (2013).  An absolute index (ab-index) to measure a researcher’s useful contributions and productivity.  PloS one, 8(12):e84334.
  * Bornmann and Daniel, (2007) Bornmann, L. and Daniel, H.-D. (2007).  Convergent validation of peer review decisions using the h index: extent of and reasons for type i and type ii errors.  Journal of Informetrics, 1(3):204–213.
  * Bornmann and Daniel, (2009) Bornmann, L. and Daniel, H.-D. (2009).  The state of h index research.  EMBO reports, 10(1):2–6.
  * Bornmann and Daniel, (2010) Bornmann, L. and Daniel, H.-D. (2010).  The citation speed index: A useful bibliometric indicator to add to the h index.  Journal of Informetrics, 4(3):444–446.
  * Bornmann et al., (2007) Bornmann, L., Mutz, R., and Daniel, H.-D. (2007).  The b index as a measure of scientific excellence.  International Journal of Scientometrics, Informetrics and Bibliometrics, 11(1.).
  * Bornmann et al., (2008) Bornmann, L., Mutz, R., and Daniel, H.-D. (2008).  Are there better indices for evaluation purposes than the h index? a comparison of nine different variants of the h index using data from biomedicine.  Journal of the American Society for Information Science and Technology, 59(5):830–837.
  * Bornmann et al., (2010) Bornmann, L., Mutz, R., and Daniel, H.-D. (2010).  The h index research output measurement: Two approaches to enhance its accuracy.  Journal of Informetrics, 4(3):407–414.
  * Bornmann et al., (2011) Bornmann, L., Mutz, R., Hug, S. E., and Daniel, H.-D. (2011).  A multilevel meta-analysis of studies reporting correlations between the h index and 37 different h index variants.  Journal of Informetrics, 5(3):346–359.
  * Bras-Amorós et al., (2011) Bras-Amorós, M., Domingo-Ferrer, J., and Torra, V. (2011).  A bibliometric index based on the collaboration distance between cited and citing authors.  Journal of Informetrics, 5(2):248–264.
  * Brown, (2009) Brown, R. J. (2009).  A simple method for excluding self-citation from the h-index: the b-index.  Online Information Review, 33(6):1129–1136.
  * Bucur et al., (2015) Bucur, O., Almasan, A., Zubarev, R., Friedman, M., Nicolson, G. L., Sumazin, P., Leabu, M., Nikolajczyk, B. S., Avram, D., Kunej, T., et al. (2015).  An updated h-index measures both the primary and total scientific output of a researcher.  Discoveries, 3(3).
  * Burrell and Rousseau, (1995) Burrell, Q. and Rousseau, R. (1995).  Fractional counts for authorship attribution: a numerical study.  Journal of the American Society for Information Science, 46(2):97.
  * (29) Burrell, Q. L. (2007a).  Hirsch’s h-index: A stochastic model.  Journal of Informetrics, 1(1):16–25.
  * (30) Burrell, Q. L. (2007b).  On the h-index, the size of the hirsch core and jin’s a-index.  Journal of Informetrics, 1(2):170–177.
  * (31) Burrell, Q. L. (2007c).  Should the h-index be discounted.  ISSI Newsletter, 3(S):65–68.
  * Cabrerizo et al., (2010) Cabrerizo, F. J., Alonso, S., Herrera-Viedma, E., and Herrera, F. (2010).  q2-index: Quantitative and qualitative evaluation based on the number and impact of papers in the hirsch core.  Journal of Informetrics, 4(1):23–28.
  * Chai et al., (2008) Chai, J., Hua, P., Rousseau, R., and Wan, J. (2008).  The adapted pure h-index.  Proceedings of WIS.
  * Chen et al., (2013) Chen, D.-z., Huang, M.-h., and Fred, Y. Y. (2013).  A probe into dynamic measures for h-core and h-tail.  Journal of Informetrics, 7(1):129–137.
  * Cole and Cole, (1973) Cole, J. R. and Cole, S. (1973).  Social stratification in science.  Chicago: U of Chicago P.
  * Cormode et al., (2013) Cormode, G., Ma, Q., Muthukrishnan, S., and Thompson, B. (2013).  Socializing the h-index.  Journal of Informetrics, 7(3):718–721.
  * Costas and Bordons, (2007) Costas, R. and Bordons, M. (2007).  The h-index: Advantages, limitations and its relation with other bibliometric indicators at the micro level.  Journal of Informetrics, 1(3):193–203.
  * de Solla Price and J., (1981) de Solla Price and J., D. (1981).  Multiple authorship.  Science, (212):986.
  * De Visscher, (2010) De Visscher, A. (2010).  An index to measure a scientist’s specific impact.  Journal of the American Society for Information Science and Technology, 61(2):319–328.
  * Ding and Cronin, (2011) Ding, Y. and Cronin, B. (2011).  Popular and/or prestigious? measures of scholarly esteem.  Information processing & management, 47(1):80–96.
  * Domingo-Ferrera and Torrab, (2011) Domingo-Ferrera, M. B.-A. J. and Torrab, V. (2011).  A bibliometric index based on the collaboration distance between cited and citing authors.
  * Dorta-González and Dorta-González, (2010) Dorta-González, P. and Dorta-González, M. I. (2010).  Indicador bibliométrico basado en el índice h.  Revista Española de Documentación Científica, 33(2):225–245.
  * Dorta-González and Dorta-González, (2011) Dorta-González, P. and Dorta-González, M.-I. (2011).  Central indexes to the citation distribution: A complement to the h-index.  Scientometrics, 88(3):729–745.
  * (44) Egghe, L. (2006a).  An improvement of the h-index: The g-index.  ISSI newsletter, 2(1):8–9.
  * (45) Egghe, L. (2006b).  Theory and practise of the g-index.  Scientometrics, 69(1):131–152.
  * Egghe, (2007) Egghe, L. (2007).  Dynamic h-index: The hirsch index in function of time.  Journal of the American Society for Information Science and Technology, 58(3):452–454.
  * Egghe, (2008) Egghe, L. (2008).  Mathematical theory of the h-and g-index in case of fractional counting of authorship.  Journal of the American Society for Information Science and Technology, 59(10):1608–1616.
  * (48) Egghe, L. (2011a).  The single publication h-index and the indirect h-index of a researcher.
  * (49) Egghe, L. (2011b).  The single publication h-index of papers in the hirsch-core of a researcher and the indirect h-index.  Scientometrics, 89(3):727–739.
  * (50) Egghe, L. (2013a).  On the correction of the h-index for career length.  Scientometrics, 96(2):563–571.
  * (51) Egghe, L. (2013b).  Theoretical justification of the central area indices and the central interval indices.  Scientometrics, 95(1):25–34.
  * Egghe and Rousseau, (2008) Egghe, L. and Rousseau, R. (2008).  An h-index weighted by citation impact.  Information Processing & Management, 44(2):770–780.
  * Egghe et al., (2000) Egghe, L., Rousseau, R., and Van Hooydonk, G. (2000).  Methods for accrediting publications to authors or countries: Consequences for evaluation studies.  Journal of the American Society for Information Science, 51(2):145–157.
  * Erlen et al., (1997) Erlen, J. A., Siminoff, L. A., Sereika, S. M., and Sutton, L. B. (1997).  Multiple authorship: issues and recommendations.  Journal of Professional Nursing, 13(4):262–270.
  * Erren and Gro$\beta$, (2016) Erren, T. C. and Gro$\beta$, J. V. (2016).  Research metrics: What about weighted citations?  Scientometrics, 107(1):315–316.
  * Fiala, (2014) Fiala, D. (2014).  Current index: A proposal for a dynamic rating system for researchers.  Journal of the Association for Information Science and Technology, 65(4):850–855.
  * Fortunato, (2014) Fortunato, S. (2014).  Author impact factor: Tracking the dynamics of individual scientific impact.
  * Franceschini et al., (2012) Franceschini, F., Galetto, M., Maisano, D., and Mastrogiacomo, L. (2012).  The success-index: an alternative approach to the h-index for evaluating an individual’s research output.  Scientometrics, 92(3):621–641.
  * (59) Franceschini, F. and Maisano, D. (2010a).  The citation triad: An overview of a scientist’s publication output based on ferrers diagrams.  Journal of Informetrics, 4(4):503–511.
  * (60) Franceschini, F. and Maisano, D. A. (2010b).  Analysis of the hirsch index’s operational properties.  European Journal of Operational Research, 203(2):494–504.
  * Fred and Rousseau, (2010) Fred, Y. Y. and Rousseau, R. (2010).  Probing the h-core: an investigation of the tail–core ratio for rank distributions.  Scientometrics, 84(2):431–439.
  * Galam, (2011) Galam, S. (2011).  Tailor based allocations for multiple authorship: a fractional gh-index.  Scientometrics, 89(1):365–379.
  * García-Pérez, (2009) García-Pérez, M. (2009).  A multidimensional extension to hirsch’s h-index.  Scientometrics, 81(3):779–785.
  * García-Pérez, (2012) García-Pérez, M. A. (2012).  An extension of the h index that covers the tail and the top of the citation curve and allows ranking researchers with similar h.  Journal of Informetrics, 6(4):689–699.
  * Glänzel, (2007) Glänzel, W. (2007).  The r-and ar-indices: Complementing the h-index-comments.  Chinese Science Bulletin, 52(6):863–863.
  * Glänzel and Schubert, (2010) Glänzel, W. and Schubert, A. (2010).  Hirsch-type characteristics of the tail of distributions. the generalised h-index.  Journal of Informetrics, 4(1):118–123.
  * Greene, (2007) Greene, M. (2007).  The demise of the lone author.  Nature, 450(7173):1165–1165.
  * Guns and Rousseau, (2009) Guns, R. and Rousseau, R. (2009).  Real and rational variants of the h-index and the g-index.  Journal of Informetrics, 3(1):64–71.
  * Hagen, (2008) Hagen, N. T. (2008).  Harmonic allocation of authorship credit: Source-level correction of bibliometric bias assures accurate publication and citation analysis.  PLoS One, 3(12):e4021.
  * Hagen, (2010) Hagen, N. T. (2010).  Harmonic publication and citation counting: sharing authorship credit equitably–not equally, geometrically or arithmetically.  Scientometrics, 84(3):785–793.
  * Harsanyi, (1993) Harsanyi, M. A. (1993).  Multiple authors, multiple problems: Bibliometrics and the study of scholarly collaboration: A literature review.  Library & Information Science Research, 15(4):325–354.
  * Harzing, (2007) Harzing, A. (2007).  Publish or perish, available from http://www.harzing.com/pop.htm.
  * Harzing, (2011) Harzing, A. (2011).  The publish or perish book: You guide to effective and responsible citation analysis.
  * Harzing et al., (2014) Harzing, A.-W., Alakangas, S., and Adams, D. (2014).  hia: An individual annual h-index to accommodate disciplinary and career length differences.  Scientometrics, 99(3):811–821.
  * Hirch, (2010) Hirch, J. (2010).  An index to quantify an individual’s scientific research output that takes into account the effect of multiple coauthorship.  Scientometrics, 85(2):741–754.
  * Hirsch, (2005) Hirsch, J. E. (2005).  An index to quantify an individual’s scientific research output.  Proceedings of the National academy of Sciences of the United States of America, pages 16569–16572.
  * Hirsch, (2007) Hirsch, J. E. (2007).  Does the h index have predictive power?  Proceedings of the National Academy of Sciences, 104(49):19193–19198.
  * Hirsch and Buela-Casal, (2014) Hirsch, J. E. and Buela-Casal, G. (2014).  The meaning of the h-index.  International Journal of Clinical and Health Psychology, 14(2):161–164.
  * Hodge et al., (1981) Hodge, S. E., Greenberg, D. A., and Challice, C. (1981).  Publication credit.  Science, 213:950.
  * Hu, (2009) Hu, X. (2009).  Loads of special authorship functions: Linear growth in the percentage of “equal first authors” and corresponding authors.  Journal of the American Society for Information Science and Technology, 60(11):2378–2381.
  * Hu et al., (2010) Hu, X., Rousseau, R., and Chen, J. (2010).  In those fields where multiple authorship is the rule, the h-index should be supplemented by role-based h-indices.  Journal of Information Science, 36(1):73–85.
  * Imperial and Rodríguez-Navarro, (2007) Imperial, J. and Rodríguez-Navarro, A. (2007).  Usefulness of hirsch’s h-index to evaluate scientific research in spain.  Scientometrics, 71(2):271–282.
  * Isola and Wolfram, (2009) Isola, A. and Wolfram, D. (2009).  Citer analysis as a measure of research impact: library and information science as a case study.  Scientometrics.
  * Jin, (2006) Jin, B. (2006).  H-index: an evaluation indicator proposed by scientist.  Science Focus, 1(1):8–9.
  * Jin, (2007) Jin, B. (2007).  The ar-index: complementing the h-index.  ISSI newsletter, 3(1):6.
  * Jin et al., (2007) Jin, B., Liang, L., Rousseau, R., and Egghe, L. (2007).  The r-and ar-indices: Complementing the h-index.  Chinese science bulletin, 52(6):855–863.
  * Katsaros et al., (2009) Katsaros, D., Akritidis, L., and Bozanis, P. (2009).  The f index: Quantifying the impact of coterminal citations on scientists’ ranking.  Journal of the American Society for Information Science and Technology, 60(5):1051–1056.
  * Kelly and Jennions, (2006) Kelly, C. D. and Jennions, M. D. (2006).  The h index and career assessment by numbers.  Trends in Ecology & Evolution, 21(4):167–170.
  * Kennedy, (2003) Kennedy, D. (2003).  Multiple authors, multiple problems.  Science, 301(5634):733–733.
  * Kosmulski, (2006) Kosmulski, M. (2006).  A new hirsch-type index saves time and works equally well as the original h-index.  ISSI newsletter, 2(3):4–6.
  * Kosmulski, (2007) Kosmulski, M. (2007).  Maxprod—a new index for assessment of the scientific output of an individual, and a comparison.  Cybermetrics, 11(1):1–5.
  * Kosmulski, (2009) Kosmulski, M. (2009).  New seniority-independent hirsch-type index.  Journal of Informetrics, 3(4):341–347.
  * (93) Kosmulski, M. (2010a).  Hirsch-type approach to the 2nd generation citations.  Journal of Informetrics, 4(3):257–264.
  * (94) Kosmulski, M. (2010b).  Hirsch-type index of international recognition.  Journal of Informetrics, 4(3):351–357.
  * Kosmulski, (2011) Kosmulski, M. (2011).  Successful papers: A new idea in evaluation of scientific output.  Journal of Informetrics, 5(3):481–485.
  * Kosmulski, (2012) Kosmulski, M. (2012).  The order in the lists of authors in multi-author papers revisited.  Journal of Informetrics, 6(4):639–644.
  * (97) Kuan, C.-H., Huang, M.-H., and Chen, D.-Z. (2011a).  Positioning research and innovation performance using shape centroids of h-core and h-tail.  Journal of Informetrics, 5(4):515–528.
  * (98) Kuan, C.-H., Huang, M.-H., and Chen, D.-Z. (2011b).  Ranking patent assignee performance by h-index and shape descriptors.  Journal of Informetrics, 5(2):303–312.
  * Lehmann et al., (2008) Lehmann, S., Jackson, A., and Lautrup, B. (2008).  A quantitative analysis of indicators of scientific performance.  Scientometrics, 76(2):369–390.
  * Lehmann et al., (2006) Lehmann, S., Jackson, A. D., and Lautrup, B. E. (2006).  Measures for measures.  Nature, 444(7122):1003–1004.
  * Liang, (2006) Liang, L. (2006).  h-index sequence and h-index matrix: Constructions and applications.  Scientometrics, 69(1):153–159.
  * Lindsey, (1980) Lindsey, D. (1980).  Production and citation measures in the sociology of science: The problem of multiple authorship.  Social Studies of Science, 10(2):145–162.
  * Liu and Fang, (2011) Liu, X. Z. and Fang, H. (2011).  Fairly sharing the credit of multi-authored papers and its application in the modification of h-index and g-index.  Scientometrics, 91(1):37–49.
  * Liu and Fang, (2012) Liu, X. Z. and Fang, H. (2012).  Modifying h-index by allocating credit of multi-authored papers whose author names rank based on contribution.  Journal of Informetrics, 6(4):557–565.
  * Liu, (2011) Liu, Y. (2011).  The diffusion of scientific ideas in time and indicators for the description of this process.
  * Liu and Rousseau, (2009) Liu, Y. and Rousseau, R. (2009).  Properties of hirsch-type indices: The case of library classification categories.  Scientometrics, 79(2):235–248.
  * Liu and Yang, (2014) Liu, Y. and Yang, Y. (2014).  Empirical study of l-sequence: The basic h-index sequence for cumulative publications with consideration of the yearly citation performance.  Journal of Informetrics, 8(3):478–485.
  * Maabreh and Alsmadi, (2012) Maabreh, M. and Alsmadi, I. M. (2012).  A survey of impact and citation indices: Limitations and issues.  International Journal of Advanced Science and Technology, 40:35–53.
  * Mahbuba and Rousseau, (2012) Mahbuba, D. and Rousseau, R. (2012).  A diffusion-based h-type indicator.  Proceedings of STI, pages 877–878.
  * Mahbuba and Rousseau, (2013) Mahbuba, D. and Rousseau, R. (2013).  Year-based h-type indicators.  Scientometrics, 96(3):785–797.
  * Martin, (1996) Martin, B. R. (1996).  The use of multiple indicators in the assessment of basic research.  Scientometrics, 36(3):343–362.
  * Mikhailov, (2012) Mikhailov, O. (2012).  A new citation index for researchers.  Herald of the Russian Academy of Sciences, 82(5):403–405.
  * Moed, (2010) Moed, H. F. (2010).  Measuring contextual citation impact of scientific journals.  Journal of Informetrics, 4(3):265–277.
  * Nair and Turlach, (2012) Nair, G. M. and Turlach, B. A. (2012).  The stochastic h-index.  Journal of Informetrics, 6(1):80–87.
  * Namazi et al., (2010) Namazi, M. R., Fallahzadeh, M. K., et al. (2010).  N-index: A novel and easily-calculable parameter for comparison of researchers working in different scientific fields.  Indian Journal of Dermatology, Venereology, and Leprology, 76(3):229.
  * Oppenheim, (1998) Oppenheim, C. (1998).  Fractional counting of multiauthored publications.  Journal of the American Society for Information Science, 49(5):482–482.
  * Pan and Fortunato, (2014) Pan, R. K. and Fortunato, S. (2014).  Author impact factor: tracking the dynamics of individual scientific impact.  Scientific reports, 4.
  * Panaretos and Malesios, (2009) Panaretos, J. and Malesios, C. (2009).  Assessing scientific research performance and impact with single indices.  Scientometrics, 81(3):635–670.
  * Prathap, (2009) Prathap, G. (2009).  Going much beyond the durfee square: enhancing the h t index.  Scientometrics, 84(1):149–152.
  * (120) Prathap, G. (2010a).  The fractional and harmonic p-indices for multiple authorship.  Scientometrics, 86(2):239–244.
  * (121) Prathap, G. (2010b).  Is there a place for a mock h-index?  Scientometrics, 84(1):153–165.
  * Riikonen and Vihinen, (2008) Riikonen, P. and Vihinen, M. (2008).  National research contributions: A case study on finnish biomedical research.  Scientometrics, 77(2):207–222.
  * Rons and Amez, (2009) Rons, N. and Amez, L. (2009).  Impact vitality: an indicator based on citing publications in search of excellent scientists.  Research Evaluation, 18(3):233–241.
  * Rons and Amez, (2013) Rons, N. and Amez, L. (2013).  Impact vitality-a measure for excellent scientists.  arXiv preprint arXiv:1307.6770.
  * Rosenberg, (2014) Rosenberg, M. S. (2014).  A biologist’s guide to impact factors.  Technical report, PeerJ PrePrints.
  * Rousseau, (2006) Rousseau, R. (2006).  New developments related to the hirsch index.
  * Rousseau, (2007) Rousseau, R. (2007).  The influence of missing publications on the hirsch index.  Journal of Informetrics, 1(1):2–7.
  * Rousseau and Fred, (2011) Rousseau, R. and Fred, Y. Y. (2011).  A simple impact measure and its evolution over time.  圖書資訊學刊, 9(2):1–10.
  * Rousseau and Leuven, (2008) Rousseau, R. and Leuven, K. (2008).  Reflections on recent developments of the h-index and h-type indices.  COLLNET Journal of Scientometrics and Information Management, 2(1):1–8.
  * Rousseau and Leydesdorff, (2011) Rousseau, R. and Leydesdorff, L. (2011).  Simple arithmetic versus intuitive understanding: The case of the impact factor.  arXiv preprint arXiv:1102.2567.
  * Rousseau and Ye, (2008) Rousseau, R. and Ye, F. Y. (2008).  A proposal for a dynamic h-type index.  Journal of the American Society for Information Science and Technology, 59(11):1853–1855.
  * Ruane and Tol, (2008) Ruane, F. and Tol, R. (2008).  Rational (successive) h-indices: An application to economics in the republic of ireland.  Scientometrics, 75(2):395–405.
  * Schreiber, (2007) Schreiber, M. (2007).  Self-citation corrections for the hirsch index.  EPL (Europhysics Letters), 78(3):30002.
  * (134) Schreiber, M. (2008a).  A modification of the h-index: The h m-index accounts for multi-authored manuscripts.  Journal of Informetrics, 2(3):211–216.
  * (135) Schreiber, M. (2008b).  To share the fame in a fair way, hm modifies h for multi-authored manuscripts.  New Journal of Physics, 10(4):040201.
  * Schreiber, (2009) Schreiber, M. (2009).  A case study of the modified hirsch index hm accounting for multiple coauthors.  Journal of the American Society for Information Science and Technology, 60(6):1274–1282.
  * (137) Schreiber, M. (2015a).  Restricting the h-index to a publication and citation time window: A case study of a timed hirsch index.  Journal of Informetrics, 9(1):150–155.
  * (138) Schreiber, M. (2015b).  A variant of the h-index to measure recent performance.  Journal of the Association for Information Science and Technology, 66(11):2373–2380.
  * Schubert, (2008) Schubert, A. (2008).  Using the h-index for assessing single publications.  Scientometrics, 78(3):559–565.
  * Schubert and Glänzel, (1986) Schubert, A. and Glänzel, W. (1986).  Mean response time—a new indicator of journal citation speed with application to physics journals.  Czechoslovak Journal of Physics, 36(1):121–125.
  * Schubert et al., (2008) Schubert, A., Korn, A., and Telcs, A. (2008).  Hirsch-type indices for characterizing networks.  Scientometrics, 78(2):375–382.
  * Sekercioglu, (2008) Sekercioglu, C. H. (2008).  Quantifying coauthor contributions.  Science, 322(5900):371.
  * Shapiro et al., (1994) Shapiro, D. W., Wenger, N. S., and Shapiro, M. F. (1994).  The contributions of authors to multiauthored biomedical research papers.  JaMa, 271(6):438–442.
  * Shtovba and Shtovba, (2015) Shtovba, S. and Shtovba, O. (2015).  Sh-index–a new fractional modification of hirsch-index.  Scientific Works of Vinnytsia National Technical University, (3).
  * Sidiropoulos et al., (2007) Sidiropoulos, A., Katsaros, D., and Manolopoulos, Y. (2007).  Generalized hirsch h-index for disclosing latent facts in citation networks.  Scientometrics, 72(2):253–280.
  * Silva et al., (2015) Silva, T. H., da Silva, A. P. C., and Moro, M. M. (2015).  Tc-index: A new research productivity index based on evolving communities.  pages 209–221.
  * Smith, (2015) Smith, D. R. (2015).  “platinum h”: Refining the h-index to more realistically assess career trajectory and scientific publications.  Archives of environmental & occupational health, 70(2):67–69.
  * Todeschini, (2011) Todeschini, R. (2011).  The j-index: a new bibliometric index and multivariate comparisons between other common indices.  Scientometrics, 87(3):621–639.
  * Todeschini and Baccini, (2016) Todeschini, R. and Baccini, A. (2016).  Handbook of bibliometric indicators: quantitative tools for studying and evaluating research.  John Wiley & Sons.
  * Tol, (2009) Tol, R. (2009).  The h-index and its alternatives: An application to the 100 most prolific economists.  Scientometrics, 80(2):317–324.
  * Tol, (2008) Tol, R. S. (2008).  A rational, successive g-index applied to economics departments in ireland.  Journal of Informetrics, 2(2):149–155.
  * Trueba and Guerrero, (2004) Trueba, F. J. and Guerrero, H. (2004).  A robust formula to credit authors for their publications.  Scientometrics, 60(2):181–204.
  * Vaidya, (2005) Vaidya, J. S. (2005).  V-index: A fairer index to quantify an individual’s research output capacity.  BMJ.
  * Van Dalen and Henkens, (2005) Van Dalen, H. P. and Henkens, K. n. (2005).  Signals in science-on the importance of signaling in gaining attention in science.  Scientometrics, 64(2):209–233.
  * Van Eck and Waltman, (2008) Van Eck, N. J. and Waltman, L. (2008).  Generalizing the h-and g-indices.  Journal of Informetrics, 2(4):263–271.
  * Van Hooydonk, (1997) Van Hooydonk, G. (1997).  Fractional counting of multiauthored publications: Consequences for the impact of authors.  Journal of the American Society for Information Science, 48(10):944–945.
  * Van Leeuwen et al., (2003) Van Leeuwen, T. N., Visser, M. S., Moed, H. F., Nederhof, T. J., and Van Raan, A. F. (2003).  The holy grail of science policy: Exploring and combining bibliometric tools in search of scientific excellence.  Scientometrics, 57(2):257–280.
  * Van Raan, (2004) Van Raan, A. F. (2004).  Sleeping beauties in science.  Scientometrics, 59(3):467–472.
  * Van Raan, (2006) Van Raan, A. F. (2006).  Comparison of the hirsch-index with standard bibliometric indicators and with peer judgment for 147 chemistry research groups.  scientometrics, 67(3):491–502.
  * Vanclay, (2007) Vanclay, J. K. (2007).  On the robustness of the h-index.  Journal of the American Society for Information Science and Technology, 58(10):1547–1550.
  * Vinkler, (2009) Vinkler, P. (2009).  The $\pi$-index: a new indicator for assessing scientific impact.  Journal of Information Science.
  * Walters, (2007) Walters, W. H. (2007).  Google scholar coverage of a multidisciplinary field.  Information processing & management, 43(4):1121–1132.
  * Waltman and van Eck, (2011) Waltman, L. and van Eck, N. J. (2011).  The inconsistency of the h-index.  arXiv preprint arXiv:1108.3901.
  * Waltman and Van Eck, (2012) Waltman, L. and Van Eck, N. J. (2012).  The inconsistency of the h-index.  Journal of the American Society for Information Science and Technology, 63(2):406–415.
  * Wan et al., (2013) Wan, J., Hua, P., and Rousseau, R. (2013).  The pure h-index: calculating an author’s h-index by taking co-authors into account. collnet.
  * Wan et al., (2007) Wan, J.-K., Hua, P.-H., and Rousseau, R. (2007).  The pure h-index: calculating an author’sh-index by taking co-authors into account.  COLLNET Journal of Scientometrics and Information Management, 1(2):1–5.
  * Wan and Liu, (2014) Wan, X. and Liu, F. (2014).  Wl-index: Leveraging citation mention number to quantify an individual’s scientific impact.  Journal of the Association for Information Science and Technology, 65(12):2509–2517.
  * Wildgaard et al., (2014) Wildgaard, L., Schneider, J. W., and Larsen, B. (2014).  A review of the characteristics of 108 author-level bibliometric indicators.  Scientometrics, 101(1):125–158.
  * Woeginger, (2008) Woeginger, G. J. (2008).  An axiomatic characterization of the hirsch-index.  Mathematical Social Sciences, 56(2):224–232.
  * Wohlin, (2009) Wohlin, C. (2009).  A new index for the citation curve of researchers.  Scientometrics, 81(2):521–533.
  * Wu, (2008) Wu, Q. (2008).  The w-index: A significant improvement of the h-index.  arXiv preprint arXiv:0805.4650.
  * Wu, (2010) Wu, Q. (2010).  The w-index: A measure to assess scientific impact by focusing on widely cited papers.  Journal of the American Society for Information Science and Technology, 61(3):609–614.
  * Würtz and Schmidt, (2016) Würtz, M. and Schmidt, M. (2016).  The stratified h-index.  Annals of epidemiology, 26(4):299–300.
  * Xu et al., (2015) Xu, F., Liu, W., and Mingers, J. (2015).  New journal classification methods based on the global h-index.  Information Processing & Management, 51(2):50–61.
  * Yaminfirooz and Gholinia, (2015) Yaminfirooz, M. and Gholinia, H. (2015).  Multiple h-index: a new scientometric indicator.  The Electronic Library, 33(3):547–556.
  * (176) Zhang, C.-T. (2009a).  The e-index, complementing the h-index for excess citations.  PLoS One, 4(5):e5429.
  * (177) Zhang, C.-T. (2009b).  A proposal for calculating weighted citations based on author rank.  EMBO reports, 10(5):416–417.
  * Zhang, (2013) Zhang, C.-T. (2013).  The h’-index, effectively improving the h-index based on the citation distribution.  PloS one, 8(4):e59912.


# Hamiltonicity, independence number, and pancyclicity

Choongbum Lee Department of Mathematics, UCLA, Los Angeles, CA, 90095. Email:
<EMAIL_ADDRESS>Research supported in part by a Samsung Scholarship.
Benny Sudakov Department of Mathematics, UCLA, Los Angeles, CA 90095. Email:
<EMAIL_ADDRESS>Research supported in part by NSF grant DMS-1101185,
NSF CAREER award DMS-0812005 and by USA-Israeli BSF grant.

###### Abstract

A graph on $n$ vertices is called pancyclic if it contains a cycle of length
$\ell$ for all $3\leq\ell\leq n$. In 1972, Erdős proved that if $G$ is a
Hamiltonian graph on $n>4k^{4}$ vertices with independence number $k$, then
$G$ is pancyclic. He then suggested that $n=\Omega(k^{2})$ should already be
enough to guarantee pancyclicity. Improving on his and some other later
results, we prove that there exists a constant $c$ such that $n>ck^{7/3}$
suffices.

##  1 Introduction

A Hamilton cycle of a graph is a cycle which passes through every vertex of
the graph exactly once, and a graph is called Hamiltonian if it contains a
Hamilton cycle. Determining whether a given graph is Hamiltonian is one of the
central questions in graph theory, and there are numerous results which
establish sufficient conditions for Hamiltonicity. For example, a celebrated
result of Dirac asserts that every graph of minimum degree at least $\lceil
n/2\rceil$ is Hamiltonian. A graph is pancyclic if it contains a cycle of
length $\ell$ for all $3\leq\ell\leq n$. By definition, every pancyclic graph
is Hamiltonian, but it is easy to see that the converse is not true.
Nevertheless, these two concepts are closely related and many nontrivial
conditions which imply Hamiltonicity also imply pancyclicity of a graph. For
instance, extending Dirac’s Theorem, Bondy [2] proved that every graph of
minimum degree at least $\left\lceil n/2\right\rceil$ either is the complete
bipartite $K_{\lceil n/2\rceil,\lfloor n/2\rfloor}$, or is pancyclic.
Moreover, in [3], he made a meta conjecture in this context which says that
almost any non-trivial condition on a graph which implies that the graph is
Hamiltonian also implies that the graph is pancyclic (there may be a simple
family of exceptional graphs).

Let the independence number $\alpha(G)$ of a graph $G$ be the order of a
maximum independent set of $G$. A classical result of Chvátal and Erdős [4]
says that every graph $G$ whose vertex connectivity (denoted $\kappa(G)$) is
at least as large as its independence number is Hamiltonian. Motivated by
Bondy’s metaconjecture, Amar, Fournier, and Germa [1] obtained several results
on the lengths of cycles in a graph $G$ that satisfies the Chvátal-Erdős
condition $\kappa(G)\geq\alpha(G)$, and conjectured that if such a graph $G$
is not bipartite then either $G=C_{5}$, or $G$ contains cycles of length
$\ell$ for all $4\leq\ell\leq n$ (Lou [9] made some partial progress towards
this conjecture). In a similar context, Jackson and Ordaz [7] conjectured that
that every graph $G$ with $\kappa(G)>\alpha(G)$ is pancyclic. Keevash and
Sudakov [8] proved that there exists an absolute constant $c$ such that
$\kappa(G)\geq c\alpha(G)$ is sufficient for pancyclicity.

In this paper, we study a relation between Hamiltonicity, pancyclicity, and
the independence number of a graph. Such relation was first studied by Erdős
[5]. In 1972, he proved a conjecture of Zarins by establishing the fact that
every Hamiltonian graph $G$ on $n\geq 4k^{4}$ vertices with $\alpha(G)\leq k$
is pancyclic (see also [6] for a different proof of a weaker bound). Erdős
also suggested that the bound $4k^{4}$ on the number of vertices is probably
not tight, and that the correct order of magnitude should be $\Omega(k^{2})$.
The following graph shows that this, if true, is indeed best possible. Let
$K_{1},\cdots,K_{k}$ be disjoint cliques of size $k-2$, where each $K_{i}$ has
two distinguished vertices $v_{i}$ and $w_{i}$. Let $G$ be the graph obtained
by connecting $v_{i}\in K_{i}$ and $w_{i+1}\in K_{i+1}$ by an edge (here
addition is modulo $k$). One can easily show that this graph is Hamiltonian,
has $k(k-2)$ vertices, and independence number $k$. However, this graph does
not contain a cycle of length $k-1$ (thus is not pancyclic), since every cycle
either is a subgraph of one of the cliques, or contains at least one vertex
from each clique $K_{i}$. The former type of cycles have length at most $k-2$,
and the later type of cycles have length at least $2k$.

Recently, Keevash and Sudakov [8] improved Erdős’ result and showed that
$n>150k^{3}$ already implies pancyclicity. Our main theorem further improves
this bound.

######  Theorem 1.1.

There exists a constant $c$ such that for every positive integer $k$, every
Hamiltonian graph on $n\geq ck^{7/3}$ vertices with $\alpha(G)\leq k$ is
pancyclic.

Suppose that one established the fact that for some function $f(k)$, every
Hamiltonian graph on $n\geq f(k)$ vertices with $\alpha(G)\leq k$ contains a
cycle of length $n-1$. Then, by iteratively applying this result, one can
easily see that for every constant $C\geq 1$, every graph on $n\geq Cf(k)$
vertices with $\alpha(G)\leq k$ contains cycles of all length between
$\frac{n}{C}$ and $n$. This simple observation were used in both [5] and [8],
where they found cycles of length linear in $n$ using this method, and then
found cycles of smaller lengths using other methods. Thus the problem finding
a cycle of length $n-1$ is a key step in proving pancyclicity. Keevash and
Sudakov suggested that if one just is interested in this problem, then the
bound between the number of vertices and independence number can be
significantly improved. More precisely, they asked whether there is an
absolute constant $c$ such that every Hamiltonian graph on $n\geq ck$ vertices
with independence number $k$ contains a cycle of length $n-1$.

Despite the fact that this bound suggested by Keevash and Sudakov is only
linear in $k$, even improving Erdős’ original estimate of $n=\Omega(k^{3})$
was not an easy task. Moreover, as we will explain in the concluding remarks,
currently the bottleneck of proving pancyclicity lies in this step of finding
a cycle of length $n-1$. Thus in order to prove Theorem 1.1, we partially
answer Keevash and Sudakov’s question for the range $n\geq ck^{7/3}$, and
combine this result with tools developed in [8]. Therefore, the main focus of
our paper will be to prove the following theorem.

######  Theorem 1.2.

There exists a constant $c$ such that for every positive integer $k$, every
Hamiltonian graph on $n\geq ck^{7/3}$ vertices with $\alpha(G)\leq k$ contains
a cycle of length $n-1$.

In Section 2, we state a slightly stronger form of Theorem 1.2, and use it to
deduce Theorem 1.1. Then in Sections 3 and 4, we prove the strengthened
version Theorem 1.2. To simplify the presentation, we often omit floor and
ceiling signs whenever these are not crucial and make no attempts to optimize
absolute constants involved.

##  2 Pancyclicity

In order to prove Theorem 1.1, we use the following slightly stronger form of
Theorem 1.2 whose proof will be given in the next two sections.

######  Theorem 2.1.

There exists a constant $c$ such that for every positive integer $k$, every
Hamiltonian graph on $n\geq ck^{7/3}$ with $\alpha(G)\leq k$ contains a cycle
of length $n-1$. Moreover, for an arbitrary fixed set of vertices $W$ of size
$|W|\leq 20k^{2}$, we can find such a cycle which contains all the vertices of
$W$.

As mentioned in the Introduction, Theorem 2.1 will be used to find cycles of
linear lengths. The following two results from [8, Theorem 1.3 and Lemma 3.2]
allows us to find cycle lengths in the range not covered by Theorem 2.1.

######  Theorem 2.2.

If $G$ is a graph with $\delta(G)\geq 300\alpha(G)$ then $G$ contains a cycle
of length $\ell$ for all $3\leq\ell\leq\delta(G)/81$.

######  Lemma 2.3.

Suppose $G$ is a graph with independence number $\alpha(G)\leq k$ and $V(G)$
is partitioned into two parts $A$ and $B$ such that

  1. (i)

$G[A]$ is Hamiltonian.

  2. (ii)

$|B|\geq 9k^{2}+k+1$, and

  3. (iii)

every vertex in $B$ has at least 2 neighbors in $A$.

Then $G$ contains a cycle of length $\ell$ for all
$2k+1+\left\lfloor\log_{2}(2k+1)\right\rfloor\leq\ell\leq|A|/2$.

Proof of Theorem 1.1. Note that the conclusion is immediate if $k=1$. Thus we
may assume that $k\geq 2$. Let $c$ be the maximum of the constant coming from
Theorem 2.1 and 300 and $G$ be Hamiltonian graph on $n=3ck^{7/3}$ vertices
such that $\alpha(G)\leq k$. By repeatedly applying Theorem 2.1 with
$W=\emptyset$, we can find cycles of length $ck^{7/3}$ to $3ck^{7/3}$.

Moreover, as we will see, by carefully using Theorem 2.1 in the previous step,
we can prepare a setup for applying Lemma 2.3. Let $C_{1}$ be the cycle of
length $n-1$ obtained by Theorem 2.1, and let $v_{1}$ be the vertex not
contained in $C_{1}$. We know that $v_{1}$ has at least 2 neighbors in
$C_{1}$. Let $W_{1}$ be arbitrary two vertices out of them. By applying
Theorem 2.1 with $W=W_{1}$, we can find a cycle $C_{2}$ of length $n-2$ which
contains $W_{1}$. Let $v_{2}$ be the vertex contained in $C_{1}$ but not in
$C_{2}$, and let $W_{2}$ be the union of $W_{1}$ and arbitrary two neighbors
of $v_{2}$ in $C_{2}$. We can repeat it $10k^{2}$ times (note that we maintain
$|W|\leq 20k^{2}$), to obtain a cycle $C_{10k^{2}}$ of length $n-10k^{2}$, and
vertices $v_{1},\cdots,v_{10k^{2}}$ so that each $v_{i}$ has at least 2
neighbors in the cycle $C_{10k^{2}}$. Since $10k^{2}\geq 9k^{2}+k+1$, by Lemma
2.3, $G$ contains a cycle of length $\ell$ for all
$2k+1+\left\lfloor\log_{2}(2k+1)\right\rfloor\leq\ell\leq(n-10k^{2})/2$.

Now we find all the remaining cycle lengths. From the graph $G$, pick one by
one, a vertex of degree less than $ck^{4/3}$, and remove it together with its
neighbors. Note that since the picked vertices form an independent set in $G$,
at most $k$ vertices will be removed. Therefore, when there are no more
vertices to pick, at least $3ck^{7/3}-k\cdot(ck^{4/3}+1)>ck^{7/3}$ vertices
remain, and the induced subgraph of $G$ on these vertices will be of minimum
degree at least $ck^{4/3}$. Since $ck^{4/3}\geq 300k\geq 300\alpha(G)$, by
Theorem 2.2, $G$ contains a cycle of length $\ell$ for all
$3\leq\ell\leq(c/81)k^{4/3}$.

By noticing the inequalities $(n-10k^{2})/2=(3ck^{7/3}-10k^{2})/2\geq
ck^{7/3}$ and $(c/81)k^{4/3}\geq 2k+1+\left\lfloor\log_{2}(2k+1)\right\rfloor$
we can see the existence of cycles of all possible lengths. ∎

##  3 A structural lemma

In Sections 3 and 4, we will prove Theorem 2.1. Given a Hamiltonian graph on
$n$ vertices, one can easily see that there are many ways one can find a cycle
of length $n-1$, if certain ‘chords’ are present in the graph. Our strategy is
to find such chords that are ‘nicely’ arranged. In particular, in this
section, we consider pairs of chords and the way they cross each other in
order to deduce some structure of our graph. Then in the next section, we
prove the main theorem by considering certain triples of chords, which we call
semi-triangles.

Throughout this section, let $G$ be a fixed graph on $n\geq 80k^{2}$ vertices
such that $\alpha(G)\leq k$, and let $W$ be a fixed set of vertices such that
$|W|\leq 20k^{2}$. Note that the bound on the number of vertices is weaker
than that of Theorem 2.1. The results developed in this section still holds
under this weaker bound, and we only need the stronger bound $n\geq ck^{7/3}$
in the next section. Since our goal is to prove the existence of a cycle of
length $n-1$, assume to the contrary that $G$ does not contain a cycle of
length $n-1$. Under these assumptions, we will prove a structural lemma on the
graph $G$ which will immediately imply a slightly weaker form of Theorem 2.1
where the bound on the number of vertices is replaced by $\Omega(k^{5/2})$. In
the next section, we will apply this structural lemma more carefully to prove
Theorem 2.1.

One of the main ingredients of the proof is the following proposition proved
by Erdős [5], whose idea has its origin in [4].

######  Proposition 3.1.

For all $1\leq i\leq 12k$, $G$ does not have a cycle of length $n-i$
containing $W$ for which all the vertices not in this cycle have degree at
least $13k$.

###### Proof.

Assume that $C$ is the vertex set of a cycle given as above and let
$X=V(G)\setminus C$. We will show that there exists a cycle of length $|C|+1$
which contains $C$. By repeatedly applying the same argument, we can show the
existence of a cycle of length $n-1$. Since this contradicts our hypothesis,
we can conclude that $G$ cannot contain a cycle as above.

Consider a vertex $x\in X$. Since $|X|\leq 12k$ and $\textrm{d}(x)\geq 13k$,
we know that the number of neighbors of $x$ in $C$ is at least $k$. Without
loss of generality, let $C=\\{1,2,\cdots,n-i\\}$, and assume that the vertices
are labeled in the order in which they appear on the cycle. Let
$w_{1},\cdots,w_{k}$ be distinct neighbors of $x$ in $C$. Then since $G$ has
independence number less than $k$, there exists two vertices $w_{i}-1,w_{j}-1$
which are adjacent (subtraction is modulo $n-i$). Then $G$ contains a cycle
$x,w_{i},w_{i}+1,\cdots,w_{j}-1,w_{i}-1,w_{i}-2,\cdots,w_{j},x$ of length
$n-i+1$. ∎

In view of Proposition 3.1, we make the following definition.

######  Definition 3.2.

Let a contradicting cycle be a cycle containing $W$, of length $n-i$ for some
$1\leq i\leq 12k$, for which all the vertices not in this cycle have degree at
least $13k$.

Thus Proposition 3.1 is equivalent to saying that $G$ does not contain a
contradicting cycle (under the assumption that $G$ does not contain a cycle of
length $n-1$). By considering several cases, we will show that there always
exists a contradicting cycle, from which we can deduce a contradiction on our
assumption that there is no cycle of length $n-1$ in $G$. The next simple
proposition will provide a set-up for this argument.

######  Proposition 3.3.

$G$ contains at most $13k^{2}$ vertices of degree less than $13k$.

###### Proof.

Assume that there exists a set $U$ of at least $13k^{2}+1$ vertices of degree
less than $13k$, and let $G^{\prime}\subset G$ be the subgraph of $G$ induced
by $U$. Take a vertex of $G^{\prime}$ of degree less than $13k$, remove it and
all its neighbors from $G^{\prime}$, and repeat the process. This produces an
independent set of size at least $\lceil(13k^{2}+1)/13k\rceil=k+1$ which is a
contradiction. ∎

Assume that we are given a Hamilton cycle of $G$. Place the vertices of $G$ on
a circle in the plane according to the order they appear in the Hamilton cycle
and label the vertices by elements in $[n]$ accordingly. Consider the
$40k^{2}$ intervals
$[1+(i-1)\lfloor\frac{n}{40k^{2}}\rfloor,i\lfloor\frac{n}{40k^{2}}\rfloor]$
for $i=1,\cdots,40k^{2}$ consisting of consecutive vertices on the cycle. Take
the intervals which only consist of vertices not in $W$ of degree at least
$13k$. Let $t$ be the number of such intervals and let
$I_{1},I_{2},\cdots,I_{t}$ be these intervals (see Figure 3). By Proposition
3.3, the number of intervals which contain a vertex from $W$ or of degree less
than $13k$ is at most $|W|+13k^{2}$, and therefore

$t\geq 40k^{2}-13k^{2}-|W|\geq 7k^{2}.$

&

RedBlue$x_{2}$$x_{1}$$y_{2}$$y_{1}$$y_{2}$$y_{1}$$x_{2}$$x_{1}$

Figure 1: Intervals $I_{i}$, and the type of edges in the graph $H$.

For each interval $I_{j}$, let $I_{j}^{\prime}$ be the set of first at most
$k+1$ odd vertices in it (thus $I_{j}^{\prime}$ is the set of all odd vertices
in $I_{j}$ if $|I_{j}|\leq 2(k+1)$). If there exists an edge inside
$I_{j}^{\prime}$ then since $I_{j}^{\prime}$ lies in an interval of length at
most $2k+2$, we can find a contradicting cycle. Therefore $I_{j}^{\prime}$ is
an independent set of size at least
$\min\\{k+1,\lfloor\frac{n}{80k^{2}}\rfloor\\}$. However, since the
independence number of the graph is at most $k$, the first case
$|I_{j}^{\prime}|=k+1$ gives us a contradiction. Therefore, we may assume that
$|I_{j}^{\prime}|\leq k$, and thus $I_{j}^{\prime}$ lies in an interval of
length at most $2k$.

Consider an auxiliary graph $H$ on the vertex set $[t]$ so that $i,j$ are
adjacent if and only if there exists an edge between $I_{i}^{\prime}$ and
$I_{j}^{\prime}$. Furthermore, color the edges of $H$ into three colors
according to the following rule (see Figure 3).

  1. (i)

Red if there exists $x_{1},x_{2}\in I_{i}^{\prime},y_{1},y_{2}\in
I_{j}^{\prime}$ such that $x_{1}<x_{2}$, $y_{1}<y_{2}$ and $x_{1}$ is adjacent
to $y_{1}$, and $x_{2}$ is adjacent to $y_{2}$.

  2. (ii)

Blue if not colored red, and there exists $x_{1},x_{2}\in
I_{i}^{\prime},y_{1},y_{2}\in I_{j}^{\prime}$ such that $x_{1}<x_{2}$,
$y_{1}<y_{2}$ and $x_{1}$ is adjacent to $y_{2}$, and $x_{2}$ is adjacent to
$y_{1}$.

  3. (iii)

Green if not colored red nor blue.

A red edge in the graph $H$ will give a cycle $x_{1}-y_{1}-x_{2}-y_{2}-x_{1}$,
see Figure 3. The length of the cycle is at least $n-4k$ since each
$I_{i}^{\prime}$ lies in an interval of length at most $2k$, and is at most
$n-2$ since there always exist vertices between $x_{1},x_{2}$ and between
$y_{1},y_{2}$. Moreover, the cycle contains the set $W$ since $W$ does not
intersect the intervals $I_{i}$. Therefore it is a contradicting cycle. Thus
we may assume that there does not exist red edges in $H$.

Consider the following drawing of the subgraph of $H$ induced by the blue
edges. First place all the vertices of the graph $G$ on the cycle along the
given order. A vertex of $H$, which corresponds to an interval $I_{i}$, will
be placed on the circle in the middle of the interval $I_{i}$. Draw a straight
line between $I_{i}$ and $I_{j}$ if there is a blue edge. Assume that there
exists a crossing in this drawing. Then this gives a situation as in Figure 3
which gives the cycle $x_{1}-y_{2}-x_{3}-y_{4}-y_{1}-x_{2}-y_{3}-x_{4}-x_{1}$.
This cycle has length at least $n-4\cdot 2k\geq n-8k$ and at most $n-4$, hence
is a contradicting cycle.

&

$y_{2}$$y_{1}$$y_{4}$$y_{3}$$x_{2}$$x_{1}$$x_{4}$$x_{3}$

Figure 2: Contradicting cycles for a red edge, and two crossing blue edges in
$H$.

Therefore, the subgraph of $H$ induced by blue edges form a planar graph. This
implies that there exists a subset of $[t]$ of size at least $t/5$ which does
not contain any blue edge (note that here we use the fact that every planar
graph is 5-colorable). By slightly abusing notation, we will only consider
these intervals, and relabel the intervals as $I_{1},\cdots,I_{s}$ where
$s\geq t/5>k^{2}$.

######  Lemma 3.4.

Let $a_{1},\cdots,a_{p}\in[s]$ be distinct integers and let $X_{a_{i}}\subset
I_{a_{i}}^{\prime}$ for all $i$. Then $X_{a_{1}}\cup\cdots\cup X_{a_{p}}$
contains an independent set of size at least

$\sum_{i=1}^{p}|X_{a_{i}}|-\frac{p(p-1)}{2}.$

###### Proof.

The proof of this lemma relies on a fact about green edges in the auxiliary
graph $H$. Assume that there exists a green edge between $i$ and $j$ in $H$.
Then by the definition, since the edge is neither red nor blue, we know that
there is no matching in $G$ of size 2 between $I_{i}^{\prime}$ and
$I_{j}^{\prime}$. Therefore there exists a vertex $v$ which covers all the
edges between $I_{i}^{\prime}$ and $I_{j}^{\prime}$.

Now consider the following process of constructing an independent set $J$.
Take $J=\emptyset$ in the beginning. At step $i$, add $X_{a_{i}}$ to the set
$J$. By the previous observation, for $j<i$, all the edges between $X_{a_{i}}$
and $X_{a_{j}}$ can be deleted by removing at most one vertex (either from
$X_{a_{i}}$ or $X_{a_{j}}$). Therefore $J\cup X_{a_{i}}$ can be made into an
independent set by removing at most $i-1$ vertices. By iterating the process,
we can obtain an independent set of size at least
$\sum_{i=1}^{p}\left(|X_{a_{i}}|-(i-1)\right)\geq\sum_{i=1}^{p}|X_{a_{i}}|-\frac{p(p-1)}{2}$.
∎

Remark. As mentioned before, this lemma already implies a weaker version of
Theorem 2.1 where the bound is replaced by $n=240k^{5/2}$. To see this, assume
that we have a graph on at least $240k^{5/2}$ vertices. Take
$X_{i}=I_{i}^{\prime}$ for $i=1,\cdots,\lceil k^{1/2}\rceil$ in this lemma and
notice that $|I_{i}^{\prime}|\geq\min\\{k+1,\lfloor 3k^{1/2}\rfloor\\}$. As we
have seen before, $|I_{i}^{\prime}|=k+1$ cannot happen. On the other hand,
$|I_{i}^{\prime}|=\lfloor 3k^{1/2}\rfloor$ implies the existence of an
independent set of size at least

$\lfloor 3k^{1/2}\rfloor\cdot\lceil k^{1/2}\rceil-\frac{\lceil
k^{1/2}\rceil(\lceil
k^{1/2}\rceil-1)}{2}\geq(3k^{1/2}-1)k^{1/2}-\frac{k+k^{1/2}}{2}>k,$

which gives a contradiction.

##  4 Proof of Theorem 2.1

In this section, we will prove Theorem 2.1 which says that there exists a
constant $c$ such that every Hamiltonian graph on $n\geq ck^{7/3}$ with
$\alpha(G)\leq k$ contains a cycle of length $n-1$. We will first focus on
proving the following relaxed statement: there exists $k_{0}$ such that for
$k\geq k_{0}$, every Hamiltonian graph on $n\geq 960k^{7/3}$ vertices with
$\alpha(G)\leq k$ contains a cycle of length $n-1$. Note that for the range
$k<k_{0}$, since there exists a constant $c^{\prime}$ such that
$c^{\prime}k^{7/3}\geq 240k^{5/2}$, by the remark at the end of the previous
section, the bound $n\geq c^{\prime}k^{7/3}$ will imply pancyclicity.
Therefore by taking $\max\\{960,c^{\prime}\\}$ as our final constant, the
result we prove in this section will in fact imply Theorem 2.1. By relaxing
the statement as above, we may assume that $k$ is large enough. This will
simplify many calculations. In particular, it allows us to ignore the floor
and ceiling signs in this section.

Now we prove the above relaxed statement using the tools we developed in the
previous section. Assume that $n\geq 960k^{7/3}$ and $k$ is large enough.
Recall that we have independent sets $I_{1}^{\prime},\cdots,I_{s}^{\prime}$
such that $s>k^{2}$ and
$|I_{i}^{\prime}|\geq\lfloor\frac{n}{80k^{2}}\rfloor\geq 12k^{1/3}$ for all
$i$. For each $i$, let $M_{i}$ and $L_{i}$ be the smaller $|I_{i}^{\prime}|/2$
vertices and larger $|I_{i}^{\prime}|/2$ vertices of $I_{i}^{\prime}$ in the
cycle order given in the previous section, and call them as the main set and
leftover set, respectively. Note that $M_{i}$ and $L_{i}$ both have size at
least $6k^{1/3}$. For a vertex $v$, call a set $M_{j}$ (or an index $j$) as a
neighboring main set of $v$ if $v$ contains a neighbor in $M_{j}$.

######  Lemma 4.1.

There exists a subcollection of indices $S\subset[s]$ such that the following
holds. For every $i\in S$, the set $M_{i}$ contains at least $3k^{1/3}$
vertices which each have at least $k$ neighboring main sets whose indices lie
in $S$.

###### Proof.

In order to find the set of indices $S$ described in the statement, consider
the process of removing the main sets which do not satisfy the condition one
by one. If the process ends before we run out of sets, then the remaining
indices will satisfy the condition.

Let $J=\emptyset$. Pick the first set $M_{i}$ which has been removed. It
contains at most $3k^{1/3}$ vertices which have at least $k$ neighboring main
sets. Since there are at least $6k^{1/3}$ vertices in $M_{i}$, we can pick
$3k^{1/3}$ vertices in $M_{i}$ which have less than $k$ neighboring main sets
and add them to $J$. For each such vertex added to $J$, remove all the
neighboring main sets of it. In this way, at each step we will increase the
size of $J$ by $3k^{1/3}$ and remove at most $1+(k-1)\cdot 3k^{1/3}$ main
sets. Now pick the first main sets among the remaining ones, and repeat what
we have done to further increase $J$.

Assume that in the end, there are no remaining sets (if this is not the case,
then we have found our set $S$). Note that $J$ is an independent set by
construction, and since $s>k^{2}$, the size of it will be at least

$3k^{1/3}\cdot\frac{k^{2}}{1+3k^{1/3}\cdot(k-1)}>k.$

This gives a contradiction and concludes the proof since the independence
number of the graph is at most $k$. ∎

From now on we will only consider sets which have indices in $S$. Let a semi-
triangle be a sequence of three indices $(p,q,r)$ in $S$ which lies in
clockwise order on the cycle, and satisfies either one of the following two
conditions (see Figure 3).

  1. (i)

Type A : there exists $x_{1},x_{2}\in I_{p}^{\prime},y_{1},y_{2}\in
I_{q}^{\prime},z_{1},z_{2}\in I_{r}^{\prime}$ such that
$x_{1}<x_{2},y_{1}<y_{2},z_{1}<z_{2}$ and
$\\{x_{1},z_{1}\\},\\{x_{2},y_{1}\\},\\{y_{2},z_{2}\\}\in E(G)$. Moreover,
there exists at least one set $I_{i}^{\prime}$ with $i\in S$ in the arc
starting at $p$ and ending at $q$ (traverse clockwise).

  2. (ii)

Type B : there exists $x_{1},x_{2}\in I_{p}^{\prime},y_{1},y_{2}\in
I_{q}^{\prime},z_{1},z_{2}\in I_{r}^{\prime}$ such that
$x_{1}<x_{2},y_{1}<y_{2},z_{1}<z_{2}$ and
$\\{x_{1},y_{1}\\},\\{x_{2},z_{1}\\},\\{y_{2},z_{2}\\}\in E(G)$.

Note that $(p,q,r)$ being a semi-triangle does not necessarily imply that
$(q,r,p)$ is also a semi-triangle. Semi-triangles are constructed so that
‘chords’ intersect in a predescribed way. This arrangement of chords will
allow us to find contradicting cycles, once we are given certain semi-
triangles in our graph. As an instance, one can see that a semi-triangle of
Type B contains a cycle $x_{1}-y_{1}-x_{2}-z_{1}-y_{2}-z_{2}-x_{1}$, see
Figure 3. Recall that each set $I_{j}^{\prime}$ lies in a consecutive interval
of length at most $2k$, and thus the length of the cycle is at least $n-6k$.
Moreover, since each set $I_{j}^{\prime}$ is defined as the set of odd
vertices in $I_{j}$, the length of the cycle is at most $n-3$ (it must miss
vertices between $x_{1}$ and $x_{2}$, $y_{1}$ and $y_{2}$, and $z_{1}$ and
$z_{2}$). Finally, since all the intervals $I_{j}$ do not intersect $W$, the
cycle is a contradicting cycle. Therefore we may assume that no such semi-
triangle exists. We will later see that one can find a contradicting cycle
even if Type A semi-triangles intersect in a certain way.

Next lemma shows that the graph $G$ contains many semi-triangles of Type A.

&

$I_{r}^{\prime}$$I_{q}^{\prime}$$I_{p}^{\prime}$$z_{2}$$z_{1}$$y_{2}$$y_{1}$$x_{2}$$x_{1}$

Figure 3: Semi-triangles of Type A and Type B respectively.

######  Lemma 4.2.

Let $M_{p}$ be a fixed main set, and let $S^{\prime}\subset S$ be a set of
indices such that at least $k^{1/3}$ vertices in $M_{p}$ have at least $k/3$
neighboring main sets in $S^{\prime}$. Then there exists a semi-triangle
$(p,q_{1},q_{2})$ of Type A such that $q_{1},q_{2}\in S^{\prime}$.

###### Proof.

Let $M_{p}$ and $S^{\prime}$ be given as in the statement. Among the sets
$M_{x}$ with indices in $S^{\prime}$, let $M_{i}$ be the closest one to
$M_{p}$ in the clockwise direction. To make sure that we get a semi-triangle
of Type A, we will remove $i$ from $S^{\prime}$ and only consider the set
$S^{\prime\prime}=S^{\prime}\setminus\\{i\\}$. Thus we will have $k/3-1$
neighboring main sets in $S^{\prime\prime}$ for each of the given vertices.

Arbitrarily select $k^{1/3}$ vertices in $M_{p}$ which have at least $k/3-1$
neighboring main sets in $S^{\prime\prime}$. Since for large $k$ we have
$k^{1/3}\cdot k^{1/3}\leq(k/3)-1$, we can assign $k^{1/3}$ neighboring main
sets to each selected vertex so that the assigned sets are distinct for
different vertices. Then for a selected vertex $v\in M_{p}$, let $J_{v}$ be
the union of the leftover sets $L_{x}$ corresponding to the $k^{1/3}$ main
sets $M_{x}$ assigned to $v$. Since each set $L_{x}$ has size at least
$6k^{1/3}$, by Lemma 3.4, $J_{v}$ contains an independent set of size at least
$k^{1/3}\cdot 6k^{1/3}-k^{2/3}/2\geq(11/2)k^{2/3}$. Denote this independent
set by $J_{v}^{\prime}$.

&

$L_{q_{2}}$$M_{q_{2}}$$L_{q_{1}}$$M_{q_{1}}$$L_{p}$$M_{p}$$I_{i}^{\prime}$$v_{2}$$v_{1}$

Figure 4: Constructing semi-triangles, Type A and B, respectively.

Since the sets $J_{v}^{\prime}$ are disjoint for different vertices, we have
$|\bigcup_{v\in M_{p}}J_{v}^{\prime}|\geq(11/2)k^{2/3}\cdot k^{1/3}\geq k+1$.
Therefore, by the restriction on the independence number there exists an edge
between $J_{v_{1}}^{\prime}$ and $J_{v_{2}}^{\prime}$ for two distinct
vertices $v_{1}$ and $v_{2}$ (the edge cannot be within one set
$J_{v}^{\prime}$ since $J_{v}^{\prime}$ is an independent set for all $v$).
Let $M_{q_{1}}$ be the main set in which the neighborhood of $v_{1}$ lies in,
and similarly define $M_{q_{2}}$ so that there exists an edge between
$L_{q_{1}}$ and $L_{q_{2}}$. Depending on the relative position of
$M_{q_{1}},M_{q_{2}}$ and $M_{p}$ on the cycle, the edge $\\{v_{1},v_{2}\\}$
will give rise to a semi-triangle of Type A or B, see Figure 3 (note that the
additional condition for semi-triangle of Type A is satisfied because we
removed the index $i$ in the beginning). Since we know that there does not
exist a semi-triangle of Type B, it should be a semi-triangle of Type A. ∎

In particular, Lemma 4.2 implies the existence of a semi-triangle $(p,q,r)$ of
Type A. Let the length of a Type A semi-triangle be the number of sets
$I_{i}^{\prime}$ with $i\in S$ in the arc that starts at $p$ and ends at $q$
(traverse clockwise). Among all the semi-triangles of Type A consider the one
which has minimum length and let this semi-triangle be $(p,q,r)$. By
definition, every semi-triangle has length at least 1, and thus we know that
there exists an index in $S$ in the arc starting at $p$ and ending at $q$
(traverse clockwise). Let $i\in S$ be such an index which is closest to $p$
(see Figure 3).

&

$I_{r}^{\prime}$$I_{q}^{\prime}$$I_{p}^{\prime}$$I_{i}^{\prime}$$I_{j}^{\prime}$$I_{k}^{\prime}$

Figure 5: Two overlapping semi-triangles which give a contradicting cycle.

Now consider the set of indices $S_{1},S_{2},S_{3}\subset S$ such that $S_{1}$
is the set of indices between $p$ and $q$, $S_{2}$ is the set of indices
between $q$ and $r$, and $S_{3}$ is the set of indices between $r$ and $p$
along the circle, all in clockwise order (see Figure 3). By pigeonhole
principle and how we constructed the indices $S$ in Lemma 4.1, there exists at
least one set out of $S_{1},S_{2},S_{3}$ such that at least $k^{1/3}$ vertices
of $M_{i}$ have at least $k/3$ neighboring main sets inside it.

If this set is $S_{1}$, then by Lemma 4.2 there exists a Type A semi-triangle
which is completely contained in the arc between $p$ and $q$, and thus has
smaller length than the semi-triangle $(p,q,r)$. Since this is impossible, we
may assume that the set mentioned above is either $S_{2}$ or $S_{3}$. In
either of the cases, by Lemma 4.2 we can find a Type A semi-triangle $(i,j,k)$
which together with $(p,q,r)$ will give a contradicting cycle, see Figure 3
(recall that each set $I_{i}^{\prime}$ lies in a consecutive interval of
length at most $2k$, and thus the length of this cycle is at least $n-12k$ and
at most $n-6$). This shows that the assumption we made at the beginning on $G$
not containing a cycle of length $n-1$ cannot hold. Therefore we have proved
Theorem 2.1.

##  5 Concluding Remarks

In this paper we proved that there exists an absolute constant $c$ such that
if $G$ is a Hamiltonian graph with $n\geq ck^{7/3}$ vertices and
$\alpha(G)\leq k$, then $G$ is pancyclic. The main ingredient of the proof was
Theorem 1.2, which partially answers a question of Keevash and Sudakov, and
tells us that under the same condition as above, $G$ contains a cycle of
length $n-1$. It seems very likely that if one can answer Keevash and
Sudakov’s question, even for $n=\Omega(k^{2})$, then one can also resolve
Erdős’ question, by using a similar approach to that of Section 2 (see Theorem
2.1, which is a strengthened version of Theorem 1.2).

Acknowledgement. We would like to thank Peter Keevash for stimulating
discussions.

## References

  * [1] D. Amar, I. Fournier, A. Germa,  Pancyclism in Chvátal-Erdős graphs,  Graphs Combin. 7 (1991), 101–112.
  * [2] J.A. Bondy,  Pancyclic graphs I,  J. Combin. Theory Ser. B 11 (1971) 80–84.
  * [3] J.A. Bondy,  Pancyclic graphs: Recent results, infinite and finite sets,  in : Colloq. Math. Soc. János Bolyai, Keszthely, Hungary, 1973, pp. 181–187.
  * [4] V. Chvátal and P. Erdős,  A note on Hamiltonian circuits,  Discrete Math 2 (1972) 111-113.
  * [5] P. Erdős,  Some problems in graph theory,  in: Hypergraph Seminar, Ohio State Univ., Columbus, Ohio, 1972, in: Lecture Notes in Math., vol. 411, Springer, Berlin, 1974, 187–190.
  * [6] E. Flandrin, H. Li, A. Marczyk, and M. Wozniak,  A note on pancyclism of highly connected graphs,  Discrete Math. 286 (2004) 57–60.
  * [7] B. Jackson, O. Ordaz,  Chvátal-Erdős conditions for paths and cycles in graphs and digraphs: A survey,  Discrete Math. 84 (1990), 241–254.
  * [8] P. Keevash and B. Sudakov,  Pancyclicity of Hamiltonian and highly connected graphs,  J. Combin. Theory Ser. B 100 (2010), 456–467.
  * [9] D. Lou,  The Chvátal-Erdős condition for cycles in triangle-free graphs,  Discrete Math. 152 (1996), 253–257.


# Analysis of the Production Strategy of Mask Types in the COVID-19
Environment

Xiangri LU  Zhanqing WANG  Hongbin MA  School of Automation, Beijing Institute
of Technology, Haidian District, Beijing

###### Abstract

Abstract. Since the outbreak of the COVID-19 in December 2019, medical
protective equipment such as disposable medical masks and KN95 masks have
become essential resources for the public. Enterprises in all sectors of
society have also transformed the production of medical masks. After the
outbreak, how to choose the right time to produce medical protective masks,
and what type of medical masks to produce will play a positive role in
preventing and controlling the epidemic in a short time. In this regard, the
evolutionary game competition analysis will be conducted through the relevant
data of disposable medical masks and KN95 masks to determine the appropriate
nodes for the production of corresponding mask types. After the research and
analysis of the production strategy of mask types, it has a positive effect on
how to guide the resumption of work and production.

###### keywords:

COVID-19,Evolutionary Game,Competition analysis,Disposable medical mask,KN95
mask

##  1 Introduction

The COVID-19 is a highly infectious disease following SARS and Middle East
Respiratory Syndrome. According to official reports, the effective way of
prevention and control is vaccination. Before the vaccine is successfully
developed, medical masks can effectively prevent the spread of the virus.
Masks are an important line of defense to prevent respiratory infectious
diseases and can reduce the risk of COVID-19[1] infection. Masks can not only
prevent the patient from spraying droplets, reduce the amount and speed of
droplets, but also block the virus-containing droplet nuclei and prevent the
wearer from inhaling, which has a good effect on controlling the epidemic.
According to statistics related to masks, the effective protection time of
ordinary disposable medical masks is 4 hours, and the effective protection
time of KN95 masks is 15 hours. The production of one KN95 mask[2,3] can
produce 3 ordinary disposable medical masks, and it can be judged that the
production of masks conforms to the evolutionary game competition model[4,5].
Starting from the production mask market system[6,7,8,9], the adjustment
behavior of the mask production group is regarded as a dynamic system, which
constitutes a macro model with a micro analysis basis, so it can more truly
reflect the diversity and complexity of the actors, and can be a macro model.
Provide a theoretical basis for regulating group behavior in the production of
masks. First of all, this article analyzes how to supply masks to front-line
medical staff from factors such as inventory support capacity, production rate
of masks, and use efficiency of different types of masks to meet the daily
consumption of three masks for all regional personnel. Secondly, this paper
designs the algorithm based on the evolutionary game algorithm and the
principle of the competition mechanism[10,11] between organisms, and uses the
Runge-Kutta method[12] to calculate the numerical solution of the mathematical
model of mask production[13] under the competition mechanism.

##  2 The Design of Production Model of Mask Type

As there are too many factors affecting the production of masks, only some
factors are considered here, and factors such as consumer purchasing power are
temporarily not considered. Assume a regional city with a population of 3
million, with 30,000 health technicians. According to the regulations of
relevant national departments, the amount of medical emergency reserve
materials should not be less than 10 days. Assuming that all 10,000 front-line
medical personnel wear KN95 masks, and the rest wear disposable protective
masks, the daily consumption of three masks per person is one time. The stock
of masks is 600,000, and the number of KN95 masks is 300,000. The second is to
define the efficiency of producing different mask types. According to market
data, the time to produce a KN95 mask can produce 3 ordinary disposable
medical masks, that is, $r_{1}=1,r_{2}=3$; ordinary disposable masks and KN95
masks The maximum production volume is three masks per person per day in the
area, that is, $n_{1}=n_{2}=900$million pieces; theoretically, the effective
protection time of ordinary disposable medical masks is 4 hours, and the
effective protection time of KN95 masks is 15 hours. In the effective
protection state, the number of KN95 masks consumed per unit time is
$s_{1}=0.27$ times that of ordinary disposable medical masks. The unit time
consumption of ordinary disposable medical masks is $s_{2}=3.75$times that of
KN95 masks.After the mask type production background model is designed, a
mathematical model is established using the population competition model.

##  3 BASIC IDEA

When the two medical resources, ordinary disposable medical masks and KN95
masks, compete for social resources and living space, the common outcome is
the extinction of weak competitiveness, and the strong competitiveness reaches
the maximum capacity allowed by the environment. Analyze the conditions that
produce various endings. Equations (1) and (2) are the differential equations
of KN95 masks and ordinary disposable medical masks in the evolution of the
amount of medical resources.

$\frac{dx}{dt}=r_{1}x\left(1+\frac{x}{n_{1}}+s_{1}\frac{y}{n_{2}}\right)$ (1)

$\frac{dy}{dt}=r_{2}y\left(1+\frac{y}{n_{2}}+s_{2}\frac{x}{n_{1}}\right)$ (2)

Where, $x(t),y(t)$ are the number of KN95 masks and ordinary disposable
medical masks that change over time, $r_{1},r_{2}$ are their production
efficiency, and $n_{1},n_{2}$ are the maximum output. $s_{1}$ is the
magnification of ordinary disposable medical masks consumed by KN95 masks per
unit time, and $s_{2}$ is the magnification of ordinary disposable medical
masks consumed per unit time of KN95 masks. The fourth-order Runge-Kutta
method is used to solve the differential equation of the number of KN95 masks
and ordinary disposable medical masks over time. First, iteratively calculate
the number of KN95 masks and ordinary disposable medical masks shown in
equations 3 and 4, and then obtain the numerical solution iterative equation
for the number of high-precision fourth-order Runge-Kutta method KN95 masks
and ordinary disposable medical masks.such as Equation 5 and Equation 6 Shown.

$x_{n+1}=x_{n}+hf(x_{n},y_{n})$ (3) $y_{n+1}=y_{n}+hf(x_{n},y_{n})$ (4)

Where $x_{n}$ represents the number of KN95 masks at time n, $y_{n}$
represents the number of ordinary disposable medical masks at time n, $h$
represents the step length of the iterative equation, and $f(x_{n},y_{n})$
represents the rate of change in the number of KN95 masks and ordinary
disposable medical masks .

$\left\\{\begin{array}[]{l}x_{n+1}=x_{n}+\frac{h}{6}\left(k_{1}+2k_{2}+2k_{3}+k_{4}\right)\\\
k_{1}=f\left(x_{n},y_{n}\right)\\\
k_{2}=f\left(x_{n}+\frac{h}{2},y_{n}+\frac{h}{2}k_{1}\right)\\\
k_{3}=f\left(x_{n}+\frac{h}{2},y_{n}+\frac{h}{2}k_{2}\right)\\\
k_{4}=f\left(x_{n}+h,y_{n}+hk_{3}\right)\end{array}\right.$ (5)
$\left\\{\begin{array}[]{l}y_{n+1}=y_{n}+\frac{h}{6}\left(k_{1}+2k_{2}+2k_{3}+k_{4}\right)\\\
k_{1}=f\left(x_{n},y_{n}\right)\\\
k_{2}=f\left(x_{n}+\frac{h}{2},y_{n}+\frac{h}{2}k_{1}\right)\\\
k_{3}=f\left(x_{n}+\frac{h}{2},y_{n}+\frac{h}{2}k_{2}\right)\\\
k_{4}=f\left(x_{n}+h,y_{n}+hk_{3}\right)\end{array}\right.$ (6)

Where $k_{1}$, $k_{2}$, $k_{3}$,$k_{4}$ are undetermined parameters. The
fourth-order Runge-Kutta method is a high-precision single-step method; the
numerical stability is good; you only need to know the first-order derivative,
and you do not need to explicitly define or calculate other higher-order
derivatives; just give $x_{n},y_{n}$ to calculate $x_{n+1},y_{n+1}$; This
article uses MATLAB to program the Runge Kuta method. The MATLAB environment
already has an integrated script for the Runge Kuta method, which is easy to
implement in programming. Through the calculation of the numerical solution of
the fourth-order Runge-Kutta method, the output changes of KN95 masks and
ordinary disposable medical masks in a part of time with a step length of 0.1
are obtained, as shown in Table 1.

Table 1: Evolution of the Number of Two Types of Masks Evolution Time | Number of KN95 | Number of disposable masks
---|---|---
0.0 | 30.000 | 60.000
0.1 | 32.972 | 76.128
0.2 | 36.207 | 95.648
0.3 | 39.719 | 118.820
0.4 | 43.522 | 145.711
0.5 | 47.626 | 176.117
0.6 | 52.043 | 209.493
0.7 | 56.781 | 244.940
0.8 | 61.851 | 281.242
0.9 | 67.261 | 316.971
1.0 | 73.023 | 350.663

##  4 SIMULATION STUDIES

In this part, we will give the production background model simulation of mask
types, and analyze the best production time nodes of KN95 masks and ordinary
disposable medical masks and how to adjust the two types of masks under the
production background model of each mask type. Output can play a positive role
in epidemic prevention.

###  4.1 situation 1

If the development of the regional mask industry is at an intermediate level,
the production background of the mask type is simulated in accordance with the
description in Section 2. The simulation results are shown in Figure 1, Figure
2. Figure 1 shows the evolutionary game confrontation between KN95 masks and
ordinary disposable medical masks. 1.8 time units before the outbreak, the
output of disposable masks had an advantage in the market. At this time, the
output of KN95 masks was steadily increasing. Between the second time unit and
the 2.8th time unit, the number of KN95 masks was still rising, but the market
share of disposable masks began to decline. After the 2.8th time unit, the
number of KN95 masks has an overwhelming advantage, and the market share of
disposable masks will be gradually replaced by KN95 masks. From the above
analysis, it can be seen that if KN95 mask manufacturers want to capture
market share at the least cost, they must start to increase the production of
KN95 masks after the second time unit. After the fifth time unit, disposable
masks have been unable to support regional fights against the epidemic. The
protective capabilities and timeliness of KN95 masks have played an important
role. At this time, KN95 masks in the region are close to saturation.
Manufacturers should adjust their production strategies according to market
demand. Slow down the production speed, and produce the corresponding number
of masks, so as to avoid excessive masks and waste.

Figure 1: Evolutionary Game of Two Types of Masks Figure 2: Two Types of Masks
Number Comparison

###  4.2 situation 2

If the development of the regional mask industry is at a high level. The
ability of regional masks to produce KN95 masks is higher than the medium
level, that is, $r_{1}=2,r_{2}=3$. The simulation images are shown in Figure 3
and Figure 4.

Figure 3: Evolutionary Game of Two Types of Masks Figure 4: Two Types of Masks
Number Comparison

Figure 3 shows the evolutionary game confrontation between KN95 masks and
ordinary disposable medical masks in high-level industrial areas. One time
unit before the outbreak of the epidemic, the output of disposable masks had
an advantage in the market. At this time, the output of KN95 masks was
steadily increasing. Between the first time unit and the 1.2th time unit, the
number of KN95 masks was still rising, but the market share of disposable
masks began to decline. After the 1.2th time unit, the number of KN95 masks
has an overwhelming advantage, and the market share of disposable masks will
be gradually replaced by KN95 masks. From the above analysis, it can be seen
that in high-level production areas, due to technological leadership, the
production efficiency of KN95 masks has been significantly improved. The time
for all regional personnel to use KN95 masks has been shortened from 9 unit
time to 4 unit time, as soon as possible The local use of masks with higher
levels of protection is more beneficial to the region’s fight against the
epidemic. In this area, the production efficiency of KN95 masks is high, and
when disposable medical masks reach 2 million in the area, the consumption is
much greater than that of KN95 masks. Manufacturers in this region can produce
9 million masks according to market demand when the epidemic breaks out to
supply all personnel in the region.

###  4.3 situation 3

If the development of the regional mask industry is at a low level. The
ability of regional masks to produce KN95 masks is lower than the medium
level, that is, $r_{1}=0.5,r_{2}=3$. The simulation images are shown in Figure
5 and Figure 6.

Figure 5: Red and Blue Evolutionary Game Confrontation Figure 6: Red and Blue
Armor Number Comparison

Figure 5 shows the evolutionary game confrontation between KN95 masks and
ordinary disposable medical masks in low-level industrial areas. 2.1 time
units before the outbreak, the output of disposable masks had an advantage in
the market. At this time, the output of KN95 masks was steadily increasing.
Between the 2.1th time unit and the 5.8th time unit, the number of KN95 masks
was still rising, but the market share of disposable masks began to decline.
After the 5.8th time unit, the number of KN95 masks has an overwhelming
advantage, and the market share of disposable masks will be gradually replaced
by KN95 masks. The production efficiency of KN95 masks is significantly
reduced in this area. The time for all regional personnel to use KN95 masks
has been lengthened from 4 unit time to 18 unit time, which is extremely
unfavorable in fighting the epidemic. At this time, a large amount of medical
disposable masks should be invested in the early stage of the fight against
the epidemic, and the output of disposable masks should be increased. When
necessary, disposable masks should be purchased across regions. According to
this situation, mask manufacturers produced a large number of disposable masks
in the early stage of the fight against the epidemic and produced a small
amount of KN95 masks. After the fight against the epidemic has experienced 6
time units, they can start producing KN95 masks. After that, they must always
pay attention to the market demand for masks. Changes, KN95 masks are produced
according to market demand changes. In summary, the key factor to obtain the
competitive advantage of KN95 masks and ordinary disposable medical masks is
to objectively analyze market demand. According to market demand, KN95 masks
and ordinary disposable medical masks are combined with the analysis of the
evolutionary game competition model. KN95 masks can be made as the trend of
regional personnel selection.

##  5 CONCLUSION

In this paper, based on the evolutionary game competition model of KN95 masks
and ordinary disposable medical masks, the mathematical model is constructed
using the principle of species competition mechanism in the evolutionary game
algorithm, and the Runge-Kutta method is used to numerically solve the
evolutionary differential equation. The evolutionary game competition between
KN95 masks and ordinary disposable medical masks, and the corresponding
relationship between the number and time of KN95 masks and ordinary disposable
medical masks is comprehensively given. In this paper, the simulation
advantage of the evolutionary game competition model of KN95 masks and
ordinary disposable medical masks is that they can grasp the trend of mask
production from a macro perspective, and provide important reference
information for fighting the epidemic.

## References

  * [1] Liang Yanru, Liu Yiqing. The evolutionary game and stability analysis of medical protective equipment market supervision under the COVID-19 epidemic[J/OL]. China Management Science: 1-11[2020-08-28].https://doi.org/10.16381 /j.cnki.issn1003-207x.2020.0448.
  * [2] Tang Guirong.Development process of key parts of KN95 mask machine[J].Metallurgical Management,2020(09):238-239.
  * [3] Ni Mingtang,Zhao Jianzhou,Fang Haoxian,Guo Zhengyuan.Study on the key technology of KN95 automatic folding mask production line based on modular design[J].Mechanical and Electrical Engineering Technology,2020,49(08):141-144.
  * [4] Ian J. G,Jean P,Shah et al. Generative adversarial nets. [C]// NIPS. 2014:2672-2680.
  * [5] Peng Yong,Gao He,Li Xinxin.Analysis of optimal profit distribution of parking spot sharing in community by game theory[J].Chinese Science and Technology Paper,2020,15(02):221-227.
  * [6] Gao Jie,Wang Chuansheng.Analysis of cooperation mechanism between supply and demand based on evolutionary game theory[J].Technology and Innovation,2020(16):31-32.
  * [7] Jiang Yusi,Li Yuan,Zhao Yapu.The predicament of masks and the innovation of production and operation models of public health products[J].Science Research Management,2020,41(06):37-46.
  * [8] Wang Yuxin.Analysis of economics phenomenon of masks[J].Modern Business and Trade Industry,2020,41(25):12-15.
  * [9] Mei Feng.Emergency reinforcement of mask production, machine tool industry bravely shoulders the heavy burden[J].World Manufacturing Technology and Equipment Market,2020(02):13-18.
  * [10] Yijie Li,Zhiming Guo,Yanyuan Xing,Guang Zhang. Modeling Wolbachia Diffusion in Mosquito Populations by Discrete Competition Model[J]. Discrete Dynamics in Nature and Society,2020,2020.
  * [11] Zhang Shuo. Research on the dynamics of the three-species competition model[D]. Shanghai Normal University, 2020.
  * [12] Li Qingyang, Wang Nengchao, Yi Dayi. Numerical analysis[M]. Beijing: Tsinghua University Press, 2008.12:288-289.
  * [13] Sinopec has opened up the entire industrial chain of mask production[J].acetaldehyde acetic acid chemical industry,2020(04):45.