American Journal of Applied Mathematics

| Peer-Reviewed |

Hamiltonicity of Mycielski Graphs

Received: 28 January 2018    Accepted: 16 February 2018    Published: 16 March 2018
Views:       Downloads:

Share This Article

Abstract

Fisher, McKenna, and Boyer showed that if a graph G is hamiltonian, then its Mycielski graph μ(G) is hamitonian. In this note, it was shown that for a bipartite graph G, if its mycielski graph μ(G) is hamiltonian, then G has a Hamilton path.

DOI 10.11648/j.ajam.20180601.14
Published in American Journal of Applied Mathematics (Volume 6, Issue 1, February 2018)
Page(s) 20-22
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Bipartite Graphs, Mycielski Graph, Hamilton Cycle, Walk

References
[1] R. Balakrishnan, S. F. Raj, Connectivity of the Mycielskian of a graph, Discrete Math. 308 (2008) 2607-2610.
[2] G. J. Chang, L. Huang, X. Zhu, Circular chromatic number of Mycielski's graph, Discrete Math. 205 (1999) 23-37.
[3] M. Chen, X. Guo, H. Li, L. Zhang, Total chromatic number of generalized Mycielski graph., Discrete Math. 334 (2014) 48–51.
[4] D. C. Fisher, P. A. McKenna, E. D. Boyer, Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski' graphs, Discrete Appl. Math. 84 (1998) 93-105.
[5] D. Hajibolhassan, X. Zhu, The circular chromatic number an Mycielski construction, J. Graph Theory 44 (2003) 106-115.
[6] L. Guo, X. Guo, Connectivity of the Mycielskian of a digraph, Appl. Math. Lett. 22 (2009) 1622-1625.
[7] W. Jarnicki, W. Myrvold, P. Saltzman, S. Wagon, Properties, proved and conjectured, of Keller, Mycielski, and queen graphs, Ars Math. Contemp. 13 (2017) 427–460.
[8] P. C. B. Lam, W. Lin, G. Gu, Z. Song, Circular chromatic number and a generalization of the construction of Mycielski, J. Combin. Theory Ser. B 89 (2003) 195-205.
[9] M. Larsen, J. Propp. D. Ullman, The fractional chromatic number of Mycielski's graphs, J. Graph Theory 19 (1995) 411-416.
[10] D. Liu, Circular chromatic number for iterated Mycielski graphs, Discrete Math. 285 (2004) 335-340.
[11] X. Liu, Z. Dang, B. Wu, The hub number, girth and Mycielski graphs, Inform. Process. Lett. 114 (2014) 561–563.
[12] H. Liu, Circular chromatic number and Mycielski graphs, Acta Math. Sci. 26B (2) (2006) 314-320.
[13] J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955) 161-162.
[14] H. P. Patil, R. Pandiya, On the total graph of Mycielski graphs, central graphs and their covering numbers, Discuss. Math. Graph Theory 33 (2013) 361–371.
[15] Y. Tang, X. Zhu, Total weight choosability of Mycielski graphs, J. Comb. Optim. 33 (2017) 165–182.
[16] D. B. West, Introduction to Graph Theory, Second Edition, Prentice Hall, Upper Saddle River, NJ (2001).
Author Information
  • College of Mathematics and System Sciences, Xinjiang University, Urumqi, P. R. China

  • College of Mathematics and System Sciences, Xinjiang University, Urumqi, P. R. China

  • Department of Mathematics, Xinjiang Institute of Engineering, Urumqi, P. R. China

Cite This Article
  • APA Style

    Shuting Cheng, Dan Wang, Xiaoping Liu. (2018). Hamiltonicity of Mycielski Graphs. American Journal of Applied Mathematics, 6(1), 20-22. https://doi.org/10.11648/j.ajam.20180601.14

    Copy | Download

    ACS Style

    Shuting Cheng; Dan Wang; Xiaoping Liu. Hamiltonicity of Mycielski Graphs. Am. J. Appl. Math. 2018, 6(1), 20-22. doi: 10.11648/j.ajam.20180601.14

    Copy | Download

    AMA Style

    Shuting Cheng, Dan Wang, Xiaoping Liu. Hamiltonicity of Mycielski Graphs. Am J Appl Math. 2018;6(1):20-22. doi: 10.11648/j.ajam.20180601.14

    Copy | Download

  • @article{10.11648/j.ajam.20180601.14,
      author = {Shuting Cheng and Dan Wang and Xiaoping Liu},
      title = {Hamiltonicity of Mycielski Graphs},
      journal = {American Journal of Applied Mathematics},
      volume = {6},
      number = {1},
      pages = {20-22},
      doi = {10.11648/j.ajam.20180601.14},
      url = {https://doi.org/10.11648/j.ajam.20180601.14},
      eprint = {https://download.sciencepg.com/pdf/10.11648.j.ajam.20180601.14},
      abstract = {Fisher, McKenna, and Boyer showed that if a graph G is hamiltonian, then its Mycielski graph μ(G) is hamitonian. In this note, it was shown that for a bipartite graph G, if its mycielski graph μ(G) is hamiltonian, then G has a Hamilton path.},
     year = {2018}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Hamiltonicity of Mycielski Graphs
    AU  - Shuting Cheng
    AU  - Dan Wang
    AU  - Xiaoping Liu
    Y1  - 2018/03/16
    PY  - 2018
    N1  - https://doi.org/10.11648/j.ajam.20180601.14
    DO  - 10.11648/j.ajam.20180601.14
    T2  - American Journal of Applied Mathematics
    JF  - American Journal of Applied Mathematics
    JO  - American Journal of Applied Mathematics
    SP  - 20
    EP  - 22
    PB  - Science Publishing Group
    SN  - 2330-006X
    UR  - https://doi.org/10.11648/j.ajam.20180601.14
    AB  - Fisher, McKenna, and Boyer showed that if a graph G is hamiltonian, then its Mycielski graph μ(G) is hamitonian. In this note, it was shown that for a bipartite graph G, if its mycielski graph μ(G) is hamiltonian, then G has a Hamilton path.
    VL  - 6
    IS  - 1
    ER  - 

    Copy | Download

  • Sections