Geodesic
Regularity and Planarity of Token Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 573-586.

Voir la notice de l'article provenant de la source Library of Science

Let G = (V, E) be a graph of order n and let 1 ≤ k lt; n be an integer. The k-token graph of G is the graph whose vertices are all the k-subsets of V, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper we characterize precisely, for each value of k, which graphs have a regular k-token graph and which connected graphs have a planar k-token graph.
Keywords: token graph, Johnson graph, regularity, planarity 
@article{DMGT_2017_37_3_a5,
     author = {Carballosa, Walter and Fabila-Monroy, Ruy and Lea\~nos, Jes\'us and Rivera, Luis Manuel},
     title = {Regularity and {Planarity} of {Token} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {573--586},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a5/}
}
TY  - JOUR
AU  - Carballosa, Walter
AU  - Fabila-Monroy, Ruy
AU  - Leaños, Jesús
AU  - Rivera, Luis Manuel
TI  - Regularity and Planarity of Token Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 573
EP  - 586
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a5/
LA  - en
ID  - DMGT_2017_37_3_a5
ER  - 
%0 Journal Article
%A Carballosa, Walter
%A Fabila-Monroy, Ruy
%A Leaños, Jesús
%A Rivera, Luis Manuel
%T Regularity and Planarity of Token Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 573-586
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a5/
%G en
%F DMGT_2017_37_3_a5
Carballosa, Walter; Fabila-Monroy, Ruy; Leaños, Jesús; Rivera, Luis Manuel. Regularity and Planarity of Token Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 573-586. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a5/

[1] J.M. Boyer and J.W. Myrvold, On the cutting edge: simplified O (n) planarity by edge addition, J. Graph Algorithms Appl. 8 (2004) 241–273. doi:10.7155/jgaa.00091

[2] M. Behzad and S.E. Mahmoodian, On topological invariants of the product of graphs, Canad. Math. Bull. 12 (1969) 175–166. doi:10.4153/CMB-1969-017-3

[3] T. Etzion and S. Bitan, On the chromatic number, colorings, and codes of the Johnson graph, Discrete Appl. Math. 70 (1996) 163–175. doi:10.1016/0166-218X(96)00104-7

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

[5] R. Graham and N. Sloane, Lower bounds for constant weight codes, IEEE Trans. Inform. Theory 26 (1980) 37–43. doi:10.1109/TIT.1980.1056141

[6] J. Guo, K. Wang and F. Li, Metric dimension of some distance-regular graphs, J. Comb. Optim. 26 (2013) 190–197. doi:10.1007/s10878-012-9459-x

[7] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969).

[8] K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930) 271–283.

[9] R.A. Liebler and C.E. Praeger, Neighbour-transitive codes in Johnson graphs, Des. Codes Cryptogr. 73 (2014) 1–25. doi:10.1007/s10623-014-9982-0

[10] B.D. McKay and A. Piperno, Practical graph isomorphism II, J. Symbolic Comput. 60 (2013) 94–112. doi:10.1016/j.jsc.2013.09.003

[11] M. Neunhöffer, and C.E. Praeger, Sporadic neighbour-transitive codes in Johnson graphs, Des. Codes Cryptogr. 72 (2014) 141–152. doi:10.1007/s10623-013-9853-0

[12] W.A. Stein, et al., Sage Mathematics Software (Version 6.8), The Sage Development Team, 2015. http://www.sagemath.org .

[13] K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937) 570–590. doi:10.1007/BF01594196