Article in volume
Authors:
Title:
Well-covered token graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(3) (2023) 767-792
Received: 2020-07-26 , Revised: 2021-02-21 , Accepted: 2021-02-22 , Available online: 2021-03-13 , https://doi.org/10.7151/dmgt.2400
Abstract:
The $k$-token graph $T_k(G)$ is the graph whose vertices are the $k$-subsets
of vertices of a graph $G$, with two vertices of $T_k(G)$ adjacent if their
symmetric difference is an edge of $G$. We explore when $T_k(G)$ is a
well-covered graph, that is, when all of its maximal independent sets have the
same cardinality. For bipartite graphs $G$, we classify when $T_k(G)$ is
well-covered. For an arbitrary graph $G$, we show that if $T_2(G)$ is
well-covered, then the girth of $G$ is at most four. We include upper and
lower bounds on the independence number of $T_k(G)$, and provide some families
of well-covered token graphs.
Keywords:
independence number, well-covered graph, token graph, double vertex graph, symmetric power of a graph
References:
- Y. Alavi, M. Behzad, P. Erdős and D.R. Lick, Double vertex graphs, J. Comb. Inf. Syst. Sci. 16 (1991) 37–50.
- Y. Alavi, D.R. Lick and J. Liu, Survey of double vertex graphs, Graphs Combin. 18 (2002) 709–715.
https://doi.org/10.1007/s003730200055 - A. Alzaga, R. Iglesias and R. Pignol, Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements, J. Combin. Theory Ser. B 100 (2010) 671–682.
https://doi.org/10.1016/j.jctb.2010.07.001 - K. Audenaert, C. Godsil, G. Royle and T. Rudolph, Symmetric squares of graphs, J. Combin. Theory Ser. B 97 (2007) 74–90.
https://doi.org/10.1016/j.jctb.2006.04.002 - A.R. Barghi and I. Ponomarenko, Non-isomorphic graphs with cospectral symmetric powers, Electron. J. Combin. 16(1) (2009) #R120..
- W. Carballosa, R. Fabila-Monroy, J. Leaños and L.M. Rivera, Regularity and planarity of token graphs, Discuss. Math. Graph Theory 37 (2017) 573–586.
https://doi.org//10.7151/dmgt.1959 - C.J. Colbourn and A. Rosa, Triple Systems (Oxford University Press, 1999).
- H. de Alba, W. Carballosa, J. Leaños and L.M. Rivera, Independence and matching numbers of some token graphs, Australas. J. Combin. 76 (2020) 387–403.
- J. Deepalakshmi, G. Marimuthu, A. Somasundaram and S. Arumugam, On the $2$-token graph of a graph, AKCE Int. J. Graphs Comb. 17 (2020) 265–268.
https://doi.org/10.1016/j.akcej.2019.05.002 - J. Earl, K.N. Vander Meulen and A. Van Tuyl, Independence complexes of well-covered circulant graphs, Exp. Math. 25 (2016) 441–451.
https://doi.org/10.1080/10586458.2015.1091753 - R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia and D.R. Wood, Token graphs, Graphs Combin. 28 (2012) 365–380.
https://doi.org/10.1007/s00373-011-1055-9 - A. Finbow, B.L. Hartnell and R.J. Nowakowski, A characterization of well-covered graphs of girth $5$ or greater, J. Combin. Theory Ser. B 57 (1993) 44–68.
https://doi.org/10.1006/jctb.1993.1005 - D. Horsley, Small embeddings of partial Steiner triple systems, J. Combin. Des. 22 (2014) 343–365.
https://doi.org/10.1002/jcd.21359 - D.R. Hughes and F.C. Piper, Design Theory (Cambridge University Press, 1985).
https://doi.org/10.1017/CBO9780511566066 - P. Jiménez-Sepúlveda and L. Rivera, Independence numbers of some double vertex graphs and pair graphs (2018).
arXiv: 1810.06354 - J. Leaños and A.L. Trujillo-Negrete, The connectivity of token graphs, Graphs Combin. 34 (2018) 777–790.
https://doi.org/10.1007/s00373-018-1913-9 - M.D. Plummer, Well-covered graphs: A survey, Quaest. Math. 16 (1993) 253–287.
https://doi.org/10.1080/16073606.1993.9631737 - L.M. Rivera and A.L. Trujillo-Negrete, Hamiltonicity of token graphs of fan graphs, Art Discrete Appl. Math. 1 (2018) #P1.07.
https://doi.org/10.26493/2590-9770.1244.720
Close