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

The number of spanning trees in \(K_n\)-complement of a bipartite graph

  • Helin Gong,
  • Yu Gong,
  • Jun Ge

摘要

For a subgraph G of a complete graph \(K_n\) K n , the \(K_n\) K n -complement of G, denoted by \(K_n-G\) K n - G , is the graph obtained from \(K_n-G\) K n - G by removing all the edges of G. In this paper, we express the number of spanning trees of the \(K_n\) K n -complement \(K_n-G\) K n - G of a bipartite graph G in terms of the determinant of the biadjcency matrices of all induced balanced bipartite subgraphs of G, which are nonsingular, and we derive formulas of the number of spanning trees of \(K_n-G\) K n - G for various important classes of bipartite graphs G, some of which generalize some previous results.