Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Tytuł pozycji:

Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs

Tytuł:
Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs
Autorzy:
Azarija, Jernej
Powiązania:
https://bibliotekanauki.pl/articles/30098147.pdf
Data publikacji:
2013-09-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Cartesian product graphs
spanning trees
number of spanning trees
inequality
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 4; 785-790
2083-5892
Język:
angielski
Prawa:
CC BY-NC-ND: Creative Commons Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 4.0
Dostawca treści:
Biblioteka Nauki
Artykuł
  Przejdź do źródła  Link otwiera się w nowym oknie
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_1 n_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)} $.

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies