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

DOI10.1016/J.DAM.2020.02.002MaRDI QIDQ2192108zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 29 June 2020

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

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

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)

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.

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.

Cites work

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

Cited in

(19)

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

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)