Hamiltonicity of Mycielski Graphs

Shuting Cheng; Dan Wang; Xiaoping Liu

doi:doi:10.11648/j.ajam.20180601.14

| Peer-Reviewed

Hamiltonicity of Mycielski Graphs

Shuting Cheng, Dan Wang, Xiaoping Liu

Published in American Journal of Applied Mathematics (Volume 6, Issue 1)

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

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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.

Published in	American Journal of Applied Mathematics (Volume 6, Issue 1)
DOI	10.11648/j.ajam.20180601.14
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), 2018. 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).

Cite This Article

Plain Text BibTeX RIS

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://article.sciencepublishinggroup.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

Author Information

Shuting Cheng

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

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

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

Download PDF

Sections

Plain Text BibTeX RIS

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://article.sciencepublishinggroup.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