UP - logo
FMF, Mathematical Library, Lj. (MAKLJ)
  • Sharp upper and lower bounds on the number of spanning trees in Cartesian product graphs
    Azarija, Jernej, 1988-
    Let ▫$G_1$▫ and ▫$G_2$▫ be simple graphs and let ▫$n_1 = |V(G_1)|$▫, ▫$m_1 = |E(G_1)|$▫, ▫$n_2 = |V(G_2)|$▫ and ▫$m_2 = |E(G_2)|$▫. In this paper we derive sharp upper and lower bounds for the number ... of spanning trees ▫$\tau$▫ in the Cartesian product ▫$G_1 \square G_2$▫ of ▫$G_1$▫ and ▫$G_2$▫. We show that: ▫$$ \tau(G_1 \square G_2) \geq \frac{2^{(n_1-1)(n_2-1)}}{n_1n_2} (\tau(G_1) n_1)^{\frac{n_2+1}{2}} (\tau(G_2)n_2)^{\frac{n_1+1}{2}}$$▫ and ▫$$\tau(G_1 \square G_2) \leq \tau(G_1)\tau(G_2) \left[ \frac{2m_1}{n_1-1} + \frac{2m_2}{n_2-1} \right]^{(n_1-1)(n_2-1)}.$$▫ We also characterize the graphs for which equality holds. As a by-product we derive a formula for the number of spanning trees in ▫$K_{n_1} \square K_{n_2}$▫ which turns out to be ▫$n_{1}^{n_1-2} n_2^{n_2-2} (n_1+n_2)^{(n_1-1)(n_2-1)}$▫.
    Source: Discussiones mathematicae. Graph theory. - ISSN 1234-3099 (Vol. 33, no. 4, 2013, str. 785-790)
    Type of material - article, component part ; adult, serious
    Publish date - 2013
    Language - english
    COBISS.SI-ID - 17466457

    Link(s):

    http://dx.doi.org/10.7151/dmgt.1698

source: Discussiones mathematicae. Graph theory. - ISSN 1234-3099 (Vol. 33, no. 4, 2013, str. 785-790)

loading ...
loading ...
loading ...

Shelf entry