Geodesic
Well-covered token graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 767-792 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 
@article{DMGT_2023_43_3_a12,
     author = {Abdelmalek, F.M. and Vander Meulen, Esther and Vander Meulen, Kevin N. and Van Tuyl, Adam},
     title = {Well-covered token graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {767--792},
     year = {2023},
     volume = {43},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a12/}
}
TY  - JOUR
AU  - Abdelmalek, F.M.
AU  - Vander Meulen, Esther
AU  - Vander Meulen, Kevin N.
AU  - Van Tuyl, Adam
TI  - Well-covered token graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 767
EP  - 792
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a12/
LA  - en
ID  - DMGT_2023_43_3_a12
ER  - 
%0 Journal Article
%A Abdelmalek, F.M.
%A Vander Meulen, Esther
%A Vander Meulen, Kevin N.
%A Van Tuyl, Adam
%T Well-covered token graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 767-792
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a12/
%G en
%F DMGT_2023_43_3_a12
Abdelmalek, F.M.; Vander Meulen, Esther; Vander Meulen, Kevin N.; Van Tuyl, Adam. Well-covered token graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 767-792. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a12/

[1] Y. Alavi, M. Behzad, P. Erdős and D.R. Lick, Double vertex graphs, J. Comb. Inf. Syst. Sci. 16 (1991) 37–50.

[2] 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

[3] 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

[4] 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

[5] A.R. Barghi and I. Ponomarenko, Non-isomorphic graphs with cospectral symmetric powers, Electron. J. Combin. 16(1) (2009) #R120..

[6] 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

[7] C.J. Colbourn and A. Rosa, Triple Systems (Oxford University Press, 1999).

[8] 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.

[9] 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

[10] 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

[11] 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

[12] 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

[13] D. Horsley, Small embeddings of partial Steiner triple systems, J. Combin. Des. 22 (2014) 343–365. https://doi.org/10.1002/jcd.21359

[14] D.R. Hughes and F.C. Piper, Design Theory (Cambridge University Press, 1985). https://doi.org/10.1017/CBO9780511566066

[15] P. Jiménez-Sepúlveda and L. Rivera, Independence numbers of some double vertex graphs and pair graphs (2018). arXiv: 1810.06354

[16] 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

[17] M.D. Plummer, Well-covered graphs: A survey, Quaest. Math. 16 (1993) 253–287. https://doi.org/10.1080/16073606.1993.9631737

[18] 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