Sharp uppper and lower bounds on the number of spanning trees in Cartesian product graphs | Zendy

Jernej Azarija | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Sharp uppper and lower bounds on the number of spanning trees in Cartesian product graphs

Author(s) -

Jernej Azarija

Publication year - 2013

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1698

Subject(s) - cartesian product , mathematics , combinatorics , spanning tree , product (mathematics) , upper and lower bounds , cartesian coordinate system , simple (philosophy) , discrete mathematics , geometry , mathematical analysis , philosophy , epistemology

Let G1 and G2 be simple graphs and let n1 = |V (G1)|, m1 = |E(G1)|, n2 = |V (G2)| and m2 = |E(G2)|. In this paper we derive sharp upper and lower bounds for the number of spanning trees τ in the Cartesian product G1 □G2 of G1 and G2. We show that: and . We also characterize the graphs for which equality holds. As a by-product we derive a formula for the number of spanning trees in Kn1 □Kn2 which turns out to be .

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research