Hamiltonicity of Mycielski Graphs
American Journal of Applied Mathematics
Volume 6, Issue 1, February 2018, Pages: 20-22
Received: Jan. 28, 2018; Accepted: Feb. 16, 2018; Published: Mar. 16, 2018
Views 870      Downloads 49
Authors
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
Article Tools
Follow on us
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.
Keywords
Bipartite Graphs, Mycielski Graph, Hamilton Cycle, Walk
To cite this article
Shuting Cheng, Dan Wang, Xiaoping Liu, Hamiltonicity of Mycielski Graphs, American Journal of Applied Mathematics. Vol. 6, No. 1, 2018, pp. 20-22. doi: 10.11648/j.ajam.20180601.14
Copyright
Copyright © 2018 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
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).
ADDRESS
Science Publishing Group
548 FASHION AVENUE
NEW YORK, NY 10018
U.S.A.
Tel: (001)347-688-8931