Top

Journal of Combinatorial Optimization

Published in:

25-07-2019

Fractional matching preclusion of the restricted HL-graphs

Authors: Shunzhe Zhang, Huiqing Liu, Dong Li, Xiaolan Hu

Published in: Journal of Combinatorial Optimization | Issue 4/2019

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

search-config

AI-assisted search

Off

Abstract

The fractional matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has no fractional perfect matchings, and the fractional strong matching preclusion number of a graph is the minimum number of edges and/or vertices whose deletion leaves a resulting graph with no fractional perfect matchings. In this paper, we determine these two numbers for the restricted HL-graphs.

previous article The -spectral radius of uniform hypergraphs concerning degrees and domination number

next article On the approximability of the two-phase knapsack problem

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

Aldred REL, Anstee RP, Locke SC (2007) Perfect matchings after vertex deletions. Discrete Math 307:3048–3054MathSciNetCrossRef

Bondy JA, Murty USR (2008) Graph theory. Springer, BerlinCrossRef

Brigham RC, Harary F, Violin EC, Yellen J (2005) Perfect-matching preclusion. Congr Numer 174:185–192MathSciNetMATH

Chedid FB (1995) On the generalized twisted cube. Inf Process Lett 55:49–52MathSciNetCrossRef

Cull P, Larson S (1991) The Möbius cubes. In: Proceedings of the 6th IEEE distributed memory computing conference, pp 699–702

Efe K (1991) A variation on the hypercube with lower diameter. IEEE Trans Comput 40:1312–1316CrossRef

Efe K (1992) The crossed cube architecture for parallel computation. IEEE Trans Parallel Distrib Syst 3:513–524CrossRef

Guichard DR (2008) Perfect matchings in pruned grid graphs. Discrete Math 308:6552–6557MathSciNetCrossRef

Hilbers PAJ, Koopman MRJ, van de Snepscheut JLA (1987) The twisted cube, PARLE: parallel architectures and languages Europe vol 1: parallel architectures. Springer, Berlin, pp 152–159CrossRef

Hong WS, Hsieh SY (2013) Extra edge connectivity of hypercube-like networks. Int J Parallel Emergent Distrib Syst 28:123–133CrossRef

Hsieh SY, Lee CW (2009) Conditional edge-fault hamiltonicity of matching composition networks. IEEE Trans Parallel Distrib Syst 20:581–592CrossRef

Lai PL, Tan JJM, Tsai CH, Hsu LH (2004) The diagnosability of the matching composition network under the comparison diagnosis model. IEEE Trans Comput 53:1064–1069CrossRef

Liu Y, Liu WW (2017) Fractional matching preclusion of graphs. J Comb Optim 34:522–533MathSciNetCrossRef

Park JH (2008) Matching preclusion problem in restricted HL-graphs and recursive circulant \(G(2^m, 4)\). J KIISE 35:60–65

Park JH, Ihm IS (2011) Strong matching preclusion. Theor Comput Sci 412:6409–6419MathSciNetCrossRef

Park JH, Ihm IS (2013) Strong matching preclusion under the conditional fault model. Discrete Appl Math 161:1093–1105MathSciNetCrossRef

Park JH, Kim HC, Lim HS (2005) Fault-hamiltonicity of hypercube-like interconnection networks. In: Proceedings of IEEE international parallel and distributed processing symposium IPDPS 2005, Denver

Park JH, Kim HC, Lim HS (2009) Many-to-many disjoint path covers in the presence of faulty elements. IEEE Trans Comput 58:528–540MathSciNetCrossRef

Park JH, Son SH (2009) Conditional matching preclusion for hypercube-like interconnection networks. Theor Comput Sci 410:2632–2640MathSciNetCrossRef

Scheinerman ER, Ullman DH (1997) Fractional graph theory: a rational approach to the theory of graphs. Wiley, New YorkMATH

Yang X, Evans DJ, Megson GM (2005) The locally twisted cubes. Int J Comput Math 82:401–413MathSciNetCrossRef

Zhou JX (2017) On \(g\)-extra connectivity of hypercube-like networks. J Comput Syst Sci 88:208–219MathSciNetCrossRef

Zhu XD (2017) A hypercube variant with small diameter. J Graph Theory 85:651–660MathSciNetCrossRef

Title: Fractional matching preclusion of the restricted HL-graphs
Authors: Shunzhe Zhang
Huiqing Liu
Dong Li
Xiaolan Hu
Publication date: 25-07-2019
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 4/2019
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00441-x

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 4/2019

On the maximum size of subfamilies of labeled set with given matching number

Multiple Canadians on the road: minimizing the distance competitive ratio

On the approximability of the two-phase knapsack problem

MapReduce machine covering problem on a small number of machines

Random walk’s correlation function for multi-objective NK landscapes and quadratic assignment problem

Generalizations of weighted matroid congestion games: pure Nash equilibrium, sensitivity analysis, and discrete convex function

Premium Partner