DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

S. Lee

Sooyeon Lee

University of Mississippi

email: slee27@go.olemiss.edu

H. Wu

Haidong Wu

University of Mississippi, Louisiana State University

email: hwu@olemiss.edu

Title:

Beta invariant and chromatic uniqueness of wheels

PDF

Source:

Discussiones Mathematicae Graph Theory 44(1) (2024) 269-280

Received: 2020-08-07 , Revised: 2021-11-30 , Accepted: 2021-11-30 , Available online: 2021-12-27 , https://doi.org/10.7151/dmgt.2444

Abstract:

A graph $G$ is chromatically unique if its chromatic polynomial completely determines the graph. An $n$-spoked wheel, $W_n$, is shown to be chromatically unique when $n\ge 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\ge 15$ since 1984, although it was shown by different 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(W_n)|$ and $\beta(M) = \beta(M(W_n))$, where $\beta(M)$ is the beta invariant of $M$, then $M \cong M(W_n)$. 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:

chromatic uniqueness of graphs, beta invariant, characteristic polynomial, 2-sum, 3-sum, matroids

References:

  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.007
  2. S. Akbari and M.R. Oboudi, Cycles are determined by their domination polynomials, Ars Combin. 116 (2014) 353–358.
  3. Z.Y. Al-Rekaby and A.J.M. Khalaf, On chromaticity of wheels, Int. J. Math. Comput. Sci. 8 (2014) 1149–1152.
  4. J. Azarija, Some Results from Algebraic Graph Theory, PhD. Thesis (University of Ljubljana, 2016).
  5. I. Beaton, J.I. Brown and B. Cameron, Independence equivalence classes of paths and cycles, Australas. J. Combin. 75 (2019) 127–145.
  6. J.K. Benashski, R.R. Martin, J.T. Moore and L. Traldi, On the {$\beta$}-invariant for graphs, Congr. Numer. 109 (1995) 211–221.
  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.033
  8. B. Bollobás, Modern Graph Theory (Springer-Verlag, New York, 1998).
  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-7
  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/BFb0070369
  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-9
  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-6
  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).
  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-z
  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.010
  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.112638
  17. N.-Z. Li and G.E. Whitehead Jr., The chromatic uniqueness of {$W_{10}$}, Discrete Math. 104 (1992) 197–199.
    https://doi.org/10.1016/0012-365X(92)90334-C
  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
  19. J.G. Oxley, On Crapo's beta invariant for matroids, Stud. Appl. Math. 66 (1982) 267–277.
    https://doi.org/10.1002/sapm1982663267
  20. J. Oxley, Matroid Theory (Oxford University Press, Oxford, 2011).
    https://doi.org/10.1093/acprof:oso/9780198566946.001.0001
  21. R.C. Read, A note on the chromatic uniqueness of {$W_{10}$}, Discrete Math. 69 (1988) 317.
    https://doi.org/10.1016/0012-365X(88)90061-1
  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-4
  23. W.T. Tutte, Connectivity in matroids, Canad. J. Math. 18 (1966) 1301–1324.
    https://doi.org/10.4153/CJM-1966-129-2
  24. H. Whitney, $2$-isomorphic graphs, Amer. J. Math. 55 (1933) 1–4.
Close