错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the algebraic connectivity of some token graphs

  • C. Dalfó,
  • M. A. Fiol

摘要

The k-token graph \(F_k(G)\) F k ( G ) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. It was proved that the algebraic connectivity of \(F_k(G)\) F k ( G ) equals the algebraic connectivity of G with a proof using random walks and interchange of processes on a weighted graph. However, no algebraic or combinatorial proof is known, and it would be a hit in the area. In this paper, we algebraically prove that the algebraic connectivity of \(F_k(G)\) F k ( G ) equals the one of G for new infinite families of graphs, such as trees, some graphs with hanging trees, and graphs with minimum degree large enough. Some examples of these families are the following: the cocktail party graph, the complement graph of a cycle, and the complete multipartite graph.