Top

Journal of Applied Mathematics and Computing

Published in:

13-07-2016 | Original Research

On the number of spanning trees in graphs with multiple edges

Authors: Hajar Sahbani, Mohamed El Marraki

Published in: Journal of Applied Mathematics and Computing | Issue 1-2/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In order to solve a problem, a usual approach is to represent it in a simple structure and bring it to some particular cases. In graph theory, this approach is used to illustrate this problem by a graph, then treat it on simple sets expressing the relations between its elements. Thus that researchers saw the appearance of spanning trees. The aim of this approach is the evaluation of the number of spanning trees in some networks which can not be find using the existing methods, such as large networks, or with multiple connections. In this paper we focus on graphs with multiple edges and we consider the multi-edges fan and wheel graphs, deriving of exact and recursive functions based on operations and geometric transformations.

previous article Assessing the impact of the environmental contamination on the transmission of Ebola virus disease (EVD)

next article Impulsive fractional boundary value problem with p-Laplace operator

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Atajan, T., Hiroshi I.: Network reliability analysis by counting the number of spanning trees. In: International Symposiumon Communications and Information Technologies (ISCIT2004 ) Sapporo,Japan (2004)

Aggarwal, K.K., Rai, S.: Reliability evaluation in computer-communication networks. IEEE Trans. Reliab. 1, 32–35 (1981)CrossRefMATH

Li, X., Huang, Z.: On the Number of Spanning Trees of Graphs and Applications of Networks. Harbin Institute of Technology Press, New York (1999)

Lemmouchi, S., Haddad, M., Kheddouci, H.: Robustness study of emerged communities from exchanges in peer-to-peer networks. Comput. Commun. 36(10), 1145–1158 (2013)CrossRef

Sahbani, H., El Marraki, M.: Reliability of the closed-chain-fan social network. In: Ficloud 2015, Rome, Italy, pp. 722–725 (2015)

Takashi, N., Motter, A.E.: Synchronization is optimal in nondiagonalizable networks. Phys. Rev. E 73, 065106(R) (2006)CrossRef

Marchal, P.: Loop-erased random walks, spanning trees and Hamiltonian cycles. Electron. Commun. Probab. 5, 39–50 (2000)MathSciNetCrossRefMATH

Diestel, R.: Graph Theory. Springer, New York (2000)MATH

Kirchhoff, G.G.: Uber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Strme gefhrt wird. Ann. Phys. Chem. 72, 497–508 (1847)CrossRef

10.

Cayley, A.: A theorem on trees. Quart. J. Math. 23, 376–378 (1889)MATH

11.

Feussner, W.: Zur Berechnung der Stromsträrke in netzförmigen Letern. Anna. Phys. 13, 1304–1329 (1902)CrossRefMATH

12.

Desjarlais, R., Molina, M.: Counting spanning trees in grid graphs. Congr. Numer. 145, 177–185 (2000)MathSciNetMATH

13.

Bogdonowicz, Z.: Formulas for the number of spanning trees in a fan. Appl. Math. Sci 2, 781–786 (2008)MathSciNet

14.

Sahbani, H., El Marraki, M.: Formula for the number of spanning tress in light graph. Appl. Math. Sci. 8(18), 865–874 (2014)MathSciNet

15.

Haghighi, M.H.S., Bibak, K.: Recursive relations for the number of spanning trees. Appl. Math. Sci 46, 2263–2269 (2009)MathSciNetMATH

16.

Boesch, F.T., Prodinger, H.: Spanning tree formulas and Chebyshev polynomials. Graphs Comb 2, 191–200 (1986)MathSciNetCrossRefMATH

17.

Comellas, F., Miralles, A., Hongxiao, L., Zhongzhi, Z.: The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs. Phys. A 392, 2803–2806 (2013)MathSciNetCrossRef

18.

Daoud, S.N.: Generating formulas of the number of spanning trees of some special graphs. Eur. Phys. J. Plus 129(7), 1–14 (2014)CrossRef

19.

Stavros, D.Nikolopoulos, Papadopoulos, C.: The number of spanning trees in Kn-complements of Quasi-threshold graphs. Graphs and Comb. 20, 383–397 (2004)MATH

20.

Myers, B.R.: Number of spanning trees in a wheel. IEEE Trans. Circuit Theory CT–18, 280–282 (1971)CrossRef

Title: On the number of spanning trees in graphs with multiple edges
Authors: Hajar Sahbani
Mohamed El Marraki
Publication date: 13-07-2016
Publisher: Springer Berlin Heidelberg
Published in: Journal of Applied Mathematics and Computing / Issue 1-2/2017
Print ISSN: 1598-5865
Electronic ISSN: 1865-2085
DOI: https://doi.org/10.1007/s12190-016-1034-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1-2/2017

Intuitionistic fuzzy tolerance graphs with application

Complete weight enumerators of a class of three-weight linear codes

Stable manifolds results for planar Hadamard fractional differential equations

Algebraic quantum synchronizable codes

Analysis of time delay in viral infection model with immune impairment

Existence and multiplicity of periodic solutions for a generalized hematopoiesis model

Premium Partner