Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs

DOI10.1016/J.DAM.2020.02.002zbMATH Open1442.05049arXiv1904.07766OpenAlexW3006059017MaRDI QIDQ2192108FDOQ2192108

Authors: Yanyan Li 

Publication date: 29 June 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Using the theory of electrical network, we first obtain a simple formula for the number of spanning trees of a complete bipartite graph containing a certain matching or a certain tree. Then we apply the effective resistance (i.e., resistance distance in graphs) to find a formula for the number of spanning trees in the nearly complete bipartite graph $G(m,n,p)=K_{m,n}-p{K}_2$ $(pleqminm,n)$, which extends a recent result by Ye and Yan who obtained the effective resistances and the number of spanning trees in $G(n,n,p)$. As a corollary, we obtain the Kirchhoff index of $G(m,n,p)$ which extends a previous result by Shi and Chen.

Full work available at URL: https://arxiv.org/abs/1904.07766

Recommendations

• Effective resistances and spanning trees in the complete bipartite graph plus a matching
• Counting spanning trees in a complete bipartite graph which contain a given spanning forest
• On the number of spanning trees of \(K^m_n \pm G\) graphs
• Computing the number of \(h\)-edge spanning forests in complete bipartite graphs
• Enumeration for spanning forests of complete bipartite graphs.

zbMATH Keywords

spanning treeeffective resistancecomplete bipartite graphelectrical network

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Resistance distance in complete \(n\)-partite graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Kirchhoff indices and the matching numbers of unicyclic graphs
• Title not available (Why is that?)
• On $W$-bases of directed graphs
• Random walks and the effective resistance of networks
• Enumerating spanning trees of graphs with an involution
• Resistance distances and Kirchhoff index of graphs with an involution
• Title not available (Why is that?)
• Random walks and the effective resistance sum rules
• Resistance distance local rules
• An Extension of Foster's Network Theorem
• The second moment of the complexity of a graph
• Resistance between two vertices of almost complete bipartite graphs
• Two-point resistances and random walks on stellated regular graphs
• Solution to a conjecture on a Nordhaus-Gaddum type result for the Kirchhoff index
• A new proof of Foster's first theorem

Cited In (18)

• Enumeration of spanning trees of complete multipartite graphs containing a fixed spanning forest
• Counting spanning trees in a complete bipartite graph which contain a given spanning forest
• Counting spanning trees in almost complete multipartite graphs
• Resistance between two vertices of almost complete bipartite graphs
• Enumeration of spanning trees containing perfect matchings in hexagonal chains with a unique kink
• Title not available (Why is that?)
• Express the number of spanning trees in term of degrees
• On two conjectures concerning spanning tree edge dependences of graphs
• The number of spanning trees in \(K_n\)-complement of a bipartite graph
• Computing the number of \(h\)-edge spanning forests in complete bipartite graphs
• Resistance distances and the Moon-type formula of a vertex-weighted complete split graph
• A type of generalized mesh-star transformation and applications in electrical networks
• Algorithmic techniques for finding resistance distances on structured graphs
• Effective resistances and spanning trees in the complete bipartite graph plus a matching
• Spanning 2-forests and resistance distance in 2-connected graphs
• Counting spanning trees of multiple complete split-like graph containing a given spanning forest
• Resistance distances in generalized join graphs
• Resistance distance-based graph invariants and spanning trees of graphs derived from the strong prism of a star

This page was built for publication: Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2192108)