On the number of spanning trees of Kn and Km, n

Moh'd Z. Abu-Sbeih

doi:10.1016/0012-365X(90)90377-T

On the number of spanning trees of K_n and K_{m, n}

Moh'd Z. Abu-Sbeih^*

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

The object of this paper is to introduce a new technique for showing that the number of labelled spanning trees of the complete bipartite graph K_{m, n} is |T(m, n)| = m^{n - 1}n^{m - 1}. As an application, we use this technique to give a new proof of Cayley's formula |T(n)| = n^{n - 2}, for the number of labelled spanning trees of the complete graph K_n.

Original language	English
Pages (from-to)	205-207
Number of pages	3
Journal	Discrete Mathematics
Volume	84
Issue number	2
DOIs	https://doi.org/10.1016/0012-365X(90)90377-T
State	Published - 1 Sep 1990

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(90)90377-T

Cite this

@article{8f4bc62b92d84cd9b50e75a18e9c8ef5,

title = "On the number of spanning trees of Kn and Km, n",

abstract = "The object of this paper is to introduce a new technique for showing that the number of labelled spanning trees of the complete bipartite graph Km, n is |T(m, n)| = mn - 1nm - 1. As an application, we use this technique to give a new proof of Cayley's formula |T(n)| = nn - 2, for the number of labelled spanning trees of the complete graph Kn.",

author = "Abu-Sbeih, \{Moh'd Z.\}",

year = "1990",

month = sep,

day = "1",

doi = "10.1016/0012-365X(90)90377-T",

language = "English",

volume = "84",

pages = "205--207",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier BV",

number = "2",

}

TY - JOUR

T1 - On the number of spanning trees of Kn and Km, n

AU - Abu-Sbeih, Moh'd Z.

PY - 1990/9/1

Y1 - 1990/9/1

N2 - The object of this paper is to introduce a new technique for showing that the number of labelled spanning trees of the complete bipartite graph Km, n is |T(m, n)| = mn - 1nm - 1. As an application, we use this technique to give a new proof of Cayley's formula |T(n)| = nn - 2, for the number of labelled spanning trees of the complete graph Kn.

AB - The object of this paper is to introduce a new technique for showing that the number of labelled spanning trees of the complete bipartite graph Km, n is |T(m, n)| = mn - 1nm - 1. As an application, we use this technique to give a new proof of Cayley's formula |T(n)| = nn - 2, for the number of labelled spanning trees of the complete graph Kn.

UR - https://www.scopus.com/pages/publications/38249017229

U2 - 10.1016/0012-365X(90)90377-T

DO - 10.1016/0012-365X(90)90377-T

M3 - Article

AN - SCOPUS:38249017229

SN - 0012-365X

VL - 84

SP - 205

EP - 207

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2