CHROMATICITY OF WHEELS WITH MISSING THREE SPOKES
DOI:
https://doi.org/10.31642/JoKMC/2018/0202013Keywords:
chromatically, WHEELSAbstract
All graph consider here are simple graphs. For a graph G, Let V(G) and E(G) be the vertex set and a edge set of graph G, respectively. The order of G is denoted by v(G), and the size of G by e(G), i.e. v(G)=|V(G)| and e(G) = |E(G)|. Let P(G,λ) (or simply P(G)) denote the chromatic polynomial of graph G. Two graphs G and H are called chromatically equivalent if P(G)=P(H), and G is called chromatically unique if P(G)=P(H) implies H isomorphic to G for any graph H [9]. A wheel W_n is a graph obtained by taking the join of K_1 and the cycle C_(n-1), edges which join K_1 to the vertices of C_(n-1) are called the spokes [2]. Let W_n be wheel of order n and let W(n,k) be the graph obtained from W_n by deleting all but k consecutive spokes, where n≥4 and 1≤k≤ n – 1. Chia [2] showed that W(n,n-2) is chromatically unique for any even integers n≥6. In [1], W(5,3) was proved to be chromatically unique. Dong and Li, [5], proved that for any odd integer n≥9,W(n,n-2) is chromatically unique, and just one graph, ( shown in Fig.1(b)) is chromatically equivalent to W(7,5), and is not isomorphic to it. It is easy to check that W(4,1) and W(5,2) are chromatically unique.Downloads
References
C. Y. Chao and E. G. Whitehead Jr., Chromatically unique graphs, Discrete Math. 26 (1979) 171-17. DOI: https://doi.org/10.1016/0012-365X(79)90107-9
G. L. Chia, The chromaticity of wheels
with missing spoke, Discrete Math. 82 (1990) 209- 212. DOI: https://doi.org/10.1016/0012-365X(90)90326-D
G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1967) 71-76. DOI: https://doi.org/10.1007/BF02992776
F. M. Dong, On the chromatic uniqueness of generalized wheel graphs, Math. Res. Exposition 10 (1990) 76 - 83 (in Chinese).
F. M. Dong and Y.P. Liu and K. M. Koh, Almost all wheels with one missing spoke are chromatically unique.
F. M. Dong, K. M. Koh and K. L. Teo, Chromatic polynomials and chromaticity of graphs, World scientific publishing co. Pte. Ltd, 2005. DOI: https://doi.org/10.1142/5814
F. M. Dong and P. Liu, All wheels with two missing consecutive spokes are chromatically unique, Discrete Math. 184 (1998) 71-85. DOI: https://doi.org/10.1016/S0012-365X(96)00288-9
E. J. Farrell, On chromatic coefficients, Discrete Math. 29 (1980) 257-264. MR81d:05029. DOI: https://doi.org/10.1016/0012-365X(80)90154-5
K.M. Koh, K. L.Teo, The search for chromatically unique graphs, Discrete Mathematics 172 (1997) 59-78. DOI: https://doi.org/10.1016/S0012-365X(96)00269-5
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Abdul Jalil M. Khalaf, Hind R. Shaaban
This work is licensed under a Creative Commons Attribution 4.0 International License.
which allows users to copy, create extracts, abstracts, and new works from the Article, alter and revise the Article, and make commercial use of the Article (including reuse and/or resale of the Article by commercial entities), provided the user gives appropriate credit (with a link to the formal publication through the relevant DOI), provides a link to the license, indicates if changes were made and the licensor is not represented as endorsing the use made of the work.