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

Well-Covered Token Graphs

Published Online: 05 May 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 27 Jun 2020
Accepted: 22 Feb 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

The k-token graph Tk(G) is the graph whose vertices are the k-subsets of vertices of a graph G, with two vertices of Tk(G) adjacent if their symmetric di erence is an edge of G. We explore when Tk(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 Tk(G) is well-covered. For an arbitrary graph G, we show that if T2(G) is well-covered, then the girth of G is at most four. We include upper and lower bounds on the independence number of Tk(G), and provide some families of well-covered token graphs.

Keywords

MSC 2010

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

[2] Y. Alavi, D.R. Lick and J. Liu, Survey of double vertex graphs, Graphs Combin. 18 (2002) 709–715. doi:10.1007/s00373020005510.1007/s003730200055Search in Google Scholar

[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. doi:10.1016/j.jctb.2010.07.00110.1016/j.jctb.2010.07.001Search in Google Scholar

[4] K. Audenaert, C. Godsil, G. Royle and T. Rudolph, Symmetric squares of graphs, J. Combin. Theory Ser. B 97 (2007) 74–90. doi:10.1016/j.jctb.2006.04.00210.1016/j.jctb.2006.04.002Search in Google Scholar

[5] A.R. Barghi and I. Ponomarenko, Non-isomorphic graphs with cospectral symmetric powers, Electron. J. Combin. 16(1) (2009) #R120. doi:10.37236/20910.37236/209Search in Google Scholar

[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. doi:/10.7151/dmgt.195910.7151/dmgt.1959Search in Google Scholar

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

[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.Search in Google Scholar

[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. doi:10.1016/j.akcej.2019.05.00210.1016/j.akcej.2019.05.002Search in Google Scholar

[10] J. Earl, K.N. Vander Meulen and A. Van Tuyl, Independence complexes of well-covered circulant graphs, Exp. Math. 25 (2016) 441–451. doi:10.1080/10586458.2015.109175310.1080/10586458.2015.1091753Search in Google Scholar

[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. doi:10.1007/s00373-011-1055-910.1007/s00373-011-1055-9Search in Google Scholar

[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. doi:10.1006/jctb.1993.100510.1006/jctb.1993.1005Search in Google Scholar

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

[14] D.R. Hughes and F.C. Piper, Design Theory (Cambridge University Press, 1985). doi:10.1017/CBO978051156606610.1017/CBO9780511566066Search in Google Scholar

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

[16] J. Leaños and A.L. Trujillo-Negrete, The connectivity of token graphs, Graphs Combin. 34 (2018) 777–790. doi:10.1007/s00373-018-1913-910.1007/s00373-018-1913-9Search in Google Scholar

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

[18] L.M. Rivera and A.L. Trujillo-Negrete, Hamiltonicity of token graphs of fan graphs, Art Discrete Appl. Math. 1 (2018) #P1.07 doi:10.26493/2590-9770.1244.72010.26493/2590-9770.1244.720Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo