The number of spanning trees of a graph
dc.contributor.author | Das, Kinkar Chandra | |
dc.contributor.author | Çevik, Ahmet Sinan | |
dc.contributor.buuauthor | Cangül, İsmail Naci | |
dc.contributor.department | Uludağ Üniversitesi/Fen-Edebiyat Fakültesi/Matematik Anabilim Dalı. | tr_TR |
dc.contributor.orcid | 0000-0002-0700-5774 | tr_TR |
dc.contributor.orcid | 0000-0003-2576-160X | tr_TR |
dc.contributor.researcherid | J-3505-2017 | tr_TR |
dc.contributor.scopusid | 57189022403 | tr_TR |
dc.date.accessioned | 2023-05-29T08:45:29Z | |
dc.date.available | 2023-05-29T08:45:29Z | |
dc.date.issued | 2013-08 | |
dc.description.abstract | Let G be a simple connected graph of order n, m edges, maximum degree Delta(1) and minimum degree delta. Li et al. (Appl. Math. Lett. 23: 286-290, 2010) gave an upper bound on number of spanning trees of a graph in terms of n, m, Delta(1) and delta: t(G) <= delta (2m-Delta(1)-delta-1/n-3)(n-3). The equality holds if and only if G congruent to K-1,K-n-1, G congruent to K-n, G congruent to K-1 boolean OR (K-1 boolean OR Kn-2) or G congruent to K-n - e, where e is any edge of K-n. Unfortunately, this upper bound is erroneous. In particular, we show that this upper bound is not true for complete graph K-n. In this paper we obtain some upper bounds on the number of spanning trees of graph G in terms of its structural parameters such as the number of vertices (n), the number of edges (m), maximum degree (Delta(1)), second maximum degree (Delta(2)), minimum degree (delta), independence number (alpha), clique number (omega). Moreover, we give the Nordhaus-Gaddum-type result for number of spanning trees. | en_US |
dc.description.sponsorship | Faculty research Fund, Sungkyunkwan University | en_US |
dc.description.sponsorship | Korean Government (2013R1A1A2009341) | en_US |
dc.description.sponsorship | Selçuk Üniversitesi | en_US |
dc.description.sponsorship | Glaucoma Research Foundation | en_US |
dc.description.sponsorship | Hong Kong Baptist University | en_US |
dc.identifier.citation | Das, K. C. vd. (2013). “The number of spanning trees of a graph”. Journal of Inequalities and Applications, 2013. | en_US |
dc.identifier.issn | 1029-242X | |
dc.identifier.scopus | 2-s2.0-84894413510 | tr_TR |
dc.identifier.uri | https://doi.org/10.1186/1029-242X-2013-395 | |
dc.identifier.uri | https://doi.org/10.1186/1029-242X-2013-395 | |
dc.identifier.uri | http://hdl.handle.net/11452/32849 | |
dc.identifier.volume | 2013 | tr_TR |
dc.identifier.wos | 000336908800001 | tr_TR |
dc.indexed.scopus | Scopus | en_US |
dc.indexed.wos | SCIE | en_US |
dc.language.iso | en | en_US |
dc.publisher | Springer | en_US |
dc.relation.bap | Uludağ Üniversitesi | tr_TR |
dc.relation.collaboration | Yurt içi | tr_TR |
dc.relation.collaboration | Yurt dışı | tr_TR |
dc.relation.journal | Journal of Inequalities and Applications | en_US |
dc.relation.publicationcategory | Makale - Uluslararası Hakemli Dergi | tr_TR |
dc.relation.tubitak | TUBİTAK | tr_TR |
dc.rights | info:eu-repo/semantics/openAccess | en_US |
dc.subject | Mathematics | en_US |
dc.subject | Graph | en_US |
dc.subject | Spanning trees | en_US |
dc.subject | Independence number | en_US |
dc.subject | Clique number | en_US |
dc.subject | First Zagreb index | en_US |
dc.subject | Molecular-orbitals | en_US |
dc.subject | Zagreb indexes | en_US |
dc.subject.scopus | Signless Laplacian; Eigenvalue; Signed Graph | en_US |
dc.subject.wos | Mathematics, applied | en_US |
dc.subject.wos | Mathematics | en_US |
dc.title | The number of spanning trees of a graph | en_US |
dc.type | Article | |
dc.wos.quartile | Q2 | en_US |