nach oben

The Journal of Supercomputing

Erschienen in:

01.07.2014

Average distance, surface area, and other structural properties of exchanged hypercubes

verfasst von: Sandi Klavžar, Meijie Ma

Erschienen in: The Journal of Supercomputing | Ausgabe 1/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Exchanged hypercubes (Loh et al. in IEEE Trans Parallel Distrib Syst 16:866–874, 2005) are spanning subgraphs of hypercubes with about one half of their edges but still with many desirable properties of hypercubes. In this paper, it is shown that distance properties of exchanged hypercubes are also comparable to the corresponding properties of hypercubes. The average distance and the surface area of exchanged hypercubes are computed and it is shown that exchanged hypercubes have asymptotically the same average distance as hypercubes. Several additional metric and other properties are also deduced and it is proved that exchanged hypercubes are prime with respect to the Cartesian product of graphs.

Vorheriger Artikel The decycling problem in hierarchical cubic networks

Nächster Artikel Comparative evaluation of platforms for parallel Ant Colony Optimization

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Angjeli A, Cheng E, Lipták L (2013) Linearly many faults in dual-cube-like networks. Theor Comput Sci 472:1–8CrossRefMATH

Braun H, Stephan FC (1993) On optimizing diameter and average distance of directed interconnected networks. IEEE Trans Comput 42:353–358CrossRefMathSciNet

Chen J-C, Tsai C-H (2011) Conditional edge-fault-tolerant Hamiltonicity of dual-cubes. Inform Sci 181:620–627CrossRefMATHMathSciNet

Cheng E, Qiu K, Shen Z (2014) The edge-centered surface area of the arrangement graph. J Comb Optim 27:49–64

Chen YW (2007) A comment on “The exchanged hypercube”. IEEE Trans Parallel Distrib Syst 18:576CrossRef

Cheng B, Fan J, Jia X, Jia J (2013) Parallel construction of independent spanning trees and an application in diagnosis on Möbius cubes. J Supercomput 65:1279–1301CrossRef

Cheng E, Qiu K, Shen Z (2011) On the surface areas and average distances of meshes and tori. Parallel Process Lett 21:61–75CrossRefMATHMathSciNet

Cheng E, Qiu K, Shen Z (2012) On the surface area of the augmented cubes. J Supercomput 61:856–868CrossRef

Dinneen MJ, Hafner PR (1994) New results for the degree/diameter problem. Networks 24:359–367CrossRefMATHMathSciNet

10.

Dobrynin AA, Entringer R, Gutman I (2001) Wiener index of trees: theory and applications. Acta Appl Math 66:211–249CrossRefMATHMathSciNet

11.

Dobrynin AA, Gutman I, Klavžar S, Žigert P (2002) Wiener index of hexagonal systems. Acta Appl Math 247–294

12.

Du Z, Ilić A (2013) On AGX conjectures regarding average eccentricity. MATCH Commun Math Comput Chem 69:597–609MATHMathSciNet

13.

Fink J (2007) Perfect matchings extend to Hamilton cycles in hypercubes. J Combin Theory Ser B 97:1074–1076CrossRefMATHMathSciNet

14.

Graham N, Harary F (1988) The number of perfect matchings in a hypercube. Appl Math Lett 1:45–48CrossRefMathSciNet

15.

Gutman I, Cruz R, Rada J (2014) Wiener index of Eulerian graphs. Discrete Appl Math 162:247–250CrossRefMathSciNet

16.

Hammack R, Imrich W, Klavžar S (2011) Handbook of product graphs, 2nd edn. CRC Press, Boca RatonMATH

17.

Hinz AM, Parisse D (2012) The average eccentricity of Sierpiński graphs. Graphs Combin 28:671–686CrossRefMATHMathSciNet

18.

Imani N, Sarbazi-Azad H, Akl SG (2009) Some topological properties of star graphs: the surface area and volume. Discret Math 309:560–569CrossRefMATHMathSciNet

19.

Imrich W, Klavžar S, Rall DF (2008) Topics in graph theory: graphs and their Cartesian products. A K Peters, Wellesley

20.

Kim J-S, Kim SW, Cheng E, Lipták L (2012) Topological properties of folded hyper-star networks. J Supercomput 59:1336–1347CrossRef

21.

Klavžar S (2013) Structure of Fibonacci cubes: a survey. J Comb Optim 25:505–522CrossRefMATHMathSciNet

22.

Klavžar S, Ma M (2014) The domination number of exchanged hypercubes. Inf Process Lett 114:159–162CrossRefMATH

23.

Klavžar S, Nadjafi-Arani MJ (2013) Wiener index versus Szeged index in networks. Discret Appl Math 161:1150–1153CrossRefMATH

24.

Kuo C-N, Chou H-H, Chang N-W, Hsieh S-Y (2013) Fault-tolerant path embedding in folded hypercubes with both node and edge faults. Theor Comput Sci 475:82–91CrossRefMATHMathSciNet

25.

Li X-J, Xu J-M (2013) Generalized measures of fault tolerance in exchanged hypercubes. Inf Process Lett 113:533–537CrossRefMATH

26.

Li Y, Peng S (2000) Dual-cubes: a new interconnection network for high-performance computer clusters. In: Proceedings of the 2000 international computer architecture, pp 51–57

27.

Li Y, Peng S, Chu W (2004) Efficient collective communications in dual-cube. J Supercomput 28:71–90CrossRefMATH

28.

Loh PKK, Hsu WJ, Pan Y (2005) The exchanged hypercube. IEEE Trans Parallel Distrib Syst 16:866–874CrossRef

29.

Ma M, Liu B (2009) Cycles embedding in exchanged hypercubes. Inf Process Lett 110:71–76CrossRefMATHMathSciNet

30.

Ma M (2010) The connectivity of exchanged hypercubes. Discret Math Algorithms Appl 2:213–220CrossRefMATH

31.

Ma M, Zhu L (2011) The super connectivity of exchanged hypercubes. Inf Process Lett 111:360–364CrossRefMATHMathSciNet

32.

Mukwembi S (2013) Average distance, independence number, and spanning trees. J Graph Theory. doi:10.1002/jgt.21758

33.

Pesek I, Rotovnik M, Vukičević D, Žerovnik J (2010) Wiener number of directed graphs and its relation to the oriented network design problem. MATCH Commun Math Comput Chem 64:727–742MATHMathSciNet

34.

Shen Z, Qiu K, Cheng E (2009) On the surface area of the \((n, k)\)-star graph. Theor Comput Sci 410:5481–5490CrossRefMATHMathSciNet

35.

Tsai T-H, Chen YC, Tan JJM. Internally disjoint paths in a variant of the hypercube. In: Chang R-S, Jain LC, Peng SL (eds) Advances in intelligent systems and applications, vol 1, SIST 20. Springer, Berlin, pp 89–96

36.

Wang S, Zhang G, Feng K (2012) Fault tolerance in \(k\)-ary \(n\)-cube networks. Theor Comput Sci 460: 34–41

37.

Wang X, Fan J, Jia X, Zhang S, Yu J (2011) Embedding meshes into twisted-cubes. Inf Sci 181:3085–3099CrossRefMATHMathSciNet

Titel: Average distance, surface area, and other structural properties of exchanged hypercubes
verfasst von: Sandi Klavžar
Meijie Ma
Publikationsdatum: 01.07.2014
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 1/2014
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-014-1153-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 1/2014

Concurrent warp execution: improving performance of GPU-likely SIMD architecture by increasing resource utilization

Some properties and algorithms for the hyper-torus network

A secure and efficient identity-based authenticated key exchange protocol for mobile client–server networks

Offloading data encryption to GPU in database systems

A queuing theory model for cloud computing

Performance analysis of cloud computing services considering resources sharing among virtual machines