The number of spanning trees of a graph

Basit Öğe Kaydı
dc.contributor.authorDas, Kinkar C.
dc.contributor.authorCevik, Ahmet S.
dc.contributor.authorCangul, Ismail N.
dc.date.accessioned2020-03-26T18:44:07Z
dc.date.available2020-03-26T18:44:07Z
dc.date.issued2013
dc.departmentSelçuk Üniversitesien_US
dc.description.abstractLet 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.sponsorshipFaculty research Fund, Sungkyunkwan University; National Research Foundation - Korean governmentKorean Government [2013R1A1A2009341]; Research Project Office of Selcuk UniversitySelcuk University; Research Project Office of Uludag UniversityUludag University; TUBITAK (The Scientific and Technological Research Council of Turkey)Turkiye Bilimsel ve Teknolojik Arastirma Kurumu (TUBITAK)en_US
dc.description.sponsorshipThe authors are grateful to the referees for their valuable comments, which lead to an improvement of the original manuscript. This paper was prepared during the first author's visit in Selcuk and Uludag Universities. Moreover, we are thankful to Mr. SA Mojallal for computing the values in Example 1. The first author is supported by the Faculty research Fund, Sungkyunkwan University, 2012 and the National Research Foundation funded by the Korean government with the grant no. 2013R1A1A2009341. The second and the third authors are both partially supported by the Research Project Offices of Selcuk and Uludag Universities, and TUBITAK (The Scientific and Technological Research Council of Turkey).en_US
dc.identifier.doi10.1186/1029-242X-2013-395en_US
dc.identifier.issn1029-242Xen_US
dc.identifier.scopusqualityQ2en_US
dc.identifier.urihttps://dx.doi.org/10.1186/1029-242X-2013-395
dc.identifier.urihttps://hdl.handle.net/20.500.12395/29944
dc.identifier.wosWOS:000336908800001en_US
dc.identifier.wosqualityQ2en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.language.isoenen_US
dc.publisherSPRINGER INTERNATIONAL PUBLISHING AGen_US
dc.relation.ispartofJOURNAL OF INEQUALITIES AND APPLICATIONSen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.selcuk20240510_oaigen_US
dc.subjectgraphen_US
dc.subjectspanning treesen_US
dc.subjectindependence numberen_US
dc.subjectclique numberen_US
dc.subjectfirst Zagreb indexen_US
dc.titleThe number of spanning trees of a graphen_US
dc.typeArticleen_US

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu