1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Beta Invariant and Chromatic Uniqueness of Wheels

Published Online: 10 Jan 2022
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 07 Aug 2020
Accepted: 30 Nov 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

A graph G is chromatically unique if its chromatic polynomial completely determines the graph. An n-spoked wheel, Wn, is shown to be chromatically unique when n ≥ 4 is even [S.-J. Xu and N.-Z. Li, The chromaticity of wheels, Discrete Math. 51 (1984) 207–212]. When n is odd, this problem is still open for n ≥ 15 since 1984, although it was shown by di erent researchers that the answer is no for n = 5, 7, yes for n = 3, 9, 11, 13, and unknown for other odd n. We use the beta invariant of matroids to prove that if M is a 3-connected matroid such that |E(M)| = |E(Wn)| and β (M) = β (M(Wn)), where β (M) is the beta invariant of M, then MM(Wn). As a consequence, if G is a 3-connected graph such that the chromatic (or flow) polynomial of G equals to the chromatic (or flow) polynomial of a wheel, then G is isomorphic to the wheel. The examples for n = 3, 5 show that the 3-connectedness condition may not be dropped. We also give a splitting formula for computing the beta invariants of general parallel connection of two matroids as well as the 3-sum of two binary matroids. This generalizes the corresponding result of Brylawski [A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc. 154 (1971) 1–22].

Keywords

MSC 2010

[1] S. Akbari, S. Alikhani and Y.-h. Peng, Characterization of graphs using domination polynomials, European J. Combin. 31 (2010) 1714–1724. https://doi.org/10.1016/j.ejc.2010.03.00710.1016/j.ejc.2010.03.007 Search in Google Scholar

[2] S. Akbari and M.R. Oboudi, Cycles are determined by their domination polynomials, Ars Combin. 116 (2014) 353–358. Search in Google Scholar

[3] Z.Y. Al-Rekaby and A.J.M. Khalaf, On chromaticity of wheels, Int. J. Math. Comput. Sci. 8 (2014) 1149–1152. Search in Google Scholar

[4] J. Azarija, Some Results from Algebraic Graph Theory, PhD. Thesis (University of Ljubljana, 2016). Search in Google Scholar

[5] I. Beaton, J.I. Brown and B. Cameron, Independence equivalence classes of paths and cycles, Australas. J. Combin. 75 (2019) 127–145. Search in Google Scholar

[6] J.K. Benashski, R.R. Martin, J.T. Moore and L. Traldi, On the β-invariant for graphs, Congr. Numer. 109 (1995) 211–221. Search in Google Scholar

[7] K. Boyer, B. Brimkov, S. English, D. Ferrero, A. Keller, R. Kirsch, M. Phillips and C. Reinhart, The zero forcing polynomial of a graph, Discrete Appl. Math. 258 (2019) 35–48. https://doi.org/10.1016/j.dam.2018.11.03310.1016/j.dam.2018.11.033 Search in Google Scholar

[8] B. Bollobás, Modern Graph Theory (Springer-Verlag, New York, 1998).10.1007/978-1-4612-0619-4 Search in Google Scholar

[9] T.H. Brylawski, A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc. 154 (1971) 1–22. https://doi.org/10.1090/S0002-9947-1971-0288039-710.1090/S0002-9947-1971-0288039-7 Search in Google Scholar

[10] C.-Y. Chao and E.G. Whitehead Jr., On chromatic equivalence of graphs, in: Theory and Applications of Graphs, Lecture Notes in Math., 642, Y. Alavi and D.R. Lick (Ed(s)), (Springer Berlin Heidelberg, 1978) 121–131. https://doi.org/10.1007/BFb007036910.1007/BFb0070369 Search in Google Scholar

[11] C.-Y. Chao and G.E. Whitehead Jr., Chromatically unique graphs, Discrete Math. 27 (1979) 171–177. https://doi.org/10.1016/0012-365X(79)90107-910.1016/0012-365X(79)90107-9 Search in Google Scholar

[12] H.H. Crapo, A higher invariant for matroids, J. Combin. Theory 2 (1967) 406–417. https://doi.org/10.1016/S0021-9800(67)80051-610.1016/S0021-9800(67)80051-6 Search in Google Scholar

[13] F.M. Dong, K.M. Koh and K.L. Teo, Chromatic Polynomials and Chromaticity of Graphs (World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005).10.1142/5814 Search in Google Scholar

[14] A. de Mier and M. Noy, On graphs determined by their Tutte polynomials, Graphs Combin. 20 (2004) 105–119. https://doi.org/10.1007/s00373-003-0534-z10.1007/s00373-003-0534-z Search in Google Scholar

[15] Y. Duan, H. Wu and Q. Yu, On chromatic and flow polynomial unique graphs, Discrete Appl. Math. 156 (2008) 2300–2309. https://doi.org/10.1016/j.dam.2007.10.01010.1016/j.dam.2007.10.010 Search in Google Scholar

[16] S. Lee and H. Wu, Bounding the beta invariant of 3-connected matroids, Discrete Math. 345 (2022) 112638. https://doi.org/10.1016/j.disc.2021.11263810.1016/j.disc.2021.112638 Search in Google Scholar

[17] N.-Z. Li and G.E. Whitehead Jr., The chromatic uniqueness of W10, Discrete Math. 104 (1992) 197–199. https://doi.org/10.1016/0012-365X(92)90334-C10.1016/0012-365X(92)90334-C Search in Google Scholar

[18] J.A. Makowsky and V. Rakita, On weakly distinguishing graph polynomials, Discrete Math. Theor. Comput. Sci. 21 (2019) 4–10. https://doi.org/10.23638/DMTCS-21-1-4 Search in Google Scholar

[19] J.G. Oxley, On Crapo’s beta invariant for matroids, Stud. Appl. Math. 66 (1982) 267–277. https://doi.org/10.1002/sapm198266326710.1002/sapm1982663267 Search in Google Scholar

[20] J. Oxley, Matroid Theory (Oxford University Press, Oxford, 2011). https://doi.org/10.1093/acprof:oso/9780198566946.001.000110.1093/acprof:oso/9780198566946.001.0001 Search in Google Scholar

[21] R.C. Read, A note on the chromatic uniqueness of W10, Discrete Math. 69 (1988) 317. https://doi.org/10.1016/0012-365X(88)90061-110.1016/0012-365X(88)90061-1 Search in Google Scholar

[22] S.-J. Xu and N.-Z. Li, The chromaticity of wheels, Discrete Math. 51 (1984) 207–212. https://doi.org/10.1016/0012-365X(84)90072-410.1016/0012-365X(84)90072-4 Search in Google Scholar

[23] W.T. Tutte, Connectivity in matroids, Canad. J. Math. 18 (1966) 1301–1324. https://doi.org/10.4153/CJM-1966-129-210.4153/CJM-1966-129-2 Search in Google Scholar

[24] H. Whitney, 2-isomorphic graphs, Amer. J. Math. 55 (1933) 1–4.10.2307/2371106 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo