On the minimum number of spanning trees in cubic multigraphs | Zendy

Zbigniew R. Bogdanowicz | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the minimum number of spanning trees in cubic multigraphs

Author(s) -

Zbigniew R. Bogdanowicz

Publication year - 2018

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.2123

Subject(s) - combinatorics , spanning tree , mathematics , conjecture , graph , cubic graph , order (exchange) , minimum degree spanning tree , degree (music) , discrete mathematics , physics , line graph , voltage graph , finance , acoustics , economics

Let G2n, H2n be two non-isomorphic connected cubic multigraphs of order 2n with parallel edges permitted but without loops. Let t(G2n), t (H2n) denote the number of spanning trees in G2n, H2n, respectively. We prove that for n ≥ 3 there is the unique G2n such that t(G2n) < t(H2n) for any H2n. Furthermore, we prove that such a graph has t(G2n = 522n−3 spanning trees. Based on our results we give a conjecture for the unique r-regular connected graph H2n of order 2n and odd degree r that minimizes the number of spanning trees.

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