Search Advanced

AIMS Mathematics

2021, Volume 6, Issue 5: 5078-5087. doi: 10.3934/math.2021300
Previous Article Next Article
Research article

Notes on Hamiltonian threshold and chain graphs

  • 1.
    Department of Mathematics, Kuwait University, Safat 13060, Kuwait
  • 2.
    Faculty of Electrical Engineering, University of Belgrade, Bulevar kralja Aleksandra 73, Belgrade, Serbia
  • 3.
    Faculty of Mathematics, University of Belgrade, Studentski trg 16, Belgrade, Serbia
  • Received: 08 November 2020 Accepted: 19 February 2021 Published: 09 March 2021

  • MSC : 05C45

  • We revisit results obtained in [1], where several necessary and necessary and sufficient conditions for a connected threshold graph to be Hamiltonian were obtained. We present these results in new forms, now stated in terms of structural parameters that uniquely define the threshold graph and we extend them to chain graphs. We also identify the chain graph with minimum number of Hamilton cycles within the class of Hamiltonian chain graphs of a given order.

    Citation: Milica Anđelić, Tamara Koledin, Zoran Stanić. Notes on Hamiltonian threshold and chain graphs[J]. AIMS Mathematics, 2021, 6(5): 5078-5087. doi: 10.3934/math.2021300

    Related Papers:

  • We revisit results obtained in [1], where several necessary and necessary and sufficient conditions for a connected threshold graph to be Hamiltonian were obtained. We present these results in new forms, now stated in terms of structural parameters that uniquely define the threshold graph and we extend them to chain graphs. We also identify the chain graph with minimum number of Hamilton cycles within the class of Hamiltonian chain graphs of a given order.


    加载中


    [1] F. Harary, U. Peled, Hamiltonian threshold graphs, Discrete Appl. Math., 16 (1987), 11–15.
    [2] N. V. R. Mahadev, U. N. Peled, Threshold Graphs and Related Topics, New York: North-Holland, 1995.
    [3] J. Moon, L. Moser, On Hamiltonian bipartite graphs, Israel J. Math., 1 (1963), 163–165.
    [4] P. Qiao, X. Zhan, The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order, J. Graph Theory, 93 (2020), 222–229.
    [5] A. Schrijver, Combinatorial Optimization-Polyhedra and Efficiency, Berlin: Springer, 2003.
    [6] Z. Stanić, Laplacian controllability for graphs with integral Laplacian spectrum, Mediterr. J. Math., 18 (2021), 35.
  • Reader Comments
  • © 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
AIMS Mathematics
1.8 3.4

Metrics

Article views(2145) PDF downloads(99) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Figures(1)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog