Conditional matching preclusion for hypercube-like interconnection networks

Jung Heum Park; Sang Hyuk Son

doi:10.1016/j.tcs.2009.02.041

Conditional matching preclusion for hypercube-like interconnection networks

Jung Heum Park, Sang Hyuk Son

Department of Electrical Engineering and Computer Science

The Catholic University of Korea

Research output: Contribution to journal › Article › peer-review

46 Scopus citations

Abstract

The conditional matching preclusion number of a graph with n vertices is the minimum number of edges whose deletion results in a graph without an isolated vertex that does not have a perfect matching if n is even, or an almost perfect matching if n is odd. We develop some general properties on conditional matching preclusion and then analyze the conditional matching preclusion numbers for some HL-graphs, hypercube-like interconnection networks.

Original language	English
Pages (from-to)	2632-2640
Number of pages	9
Journal	Theoretical Computer Science
Volume	410
Issue number	27-29
DOIs	https://doi.org/10.1016/j.tcs.2009.02.041
State	Published - 28 Jun 2009

Bibliographical note

Funding Information:
This work was done when the first author was visiting Department of Computer Science, University of Virginia. This work was supported by the Catholic University of Korea, Research Fund, 2008. Corresponding author. Tel.: +82 2 2164 4366. E-mail addresses: [email protected] (J.-H. Park), [email protected] (S.H. Son).

Keywords

Almost perfect matching
Conditional fault
Edge fault
Fault tolerance
HL-graphs
Perfect matching
Restricted HL-graphs

Access to Document

10.1016/j.tcs.2009.02.041

Cite this

@article{43a6c24ba2174b96ac08e4a5a501bcc5,

title = "Conditional matching preclusion for hypercube-like interconnection networks",

abstract = "The conditional matching preclusion number of a graph with n vertices is the minimum number of edges whose deletion results in a graph without an isolated vertex that does not have a perfect matching if n is even, or an almost perfect matching if n is odd. We develop some general properties on conditional matching preclusion and then analyze the conditional matching preclusion numbers for some HL-graphs, hypercube-like interconnection networks.",

keywords = "Almost perfect matching, Conditional fault, Edge fault, Fault tolerance, HL-graphs, Perfect matching, Restricted HL-graphs",

author = "Park, {Jung Heum} and Son, {Sang Hyuk}",

note = "Funding Information: This work was done when the first author was visiting Department of Computer Science, University of Virginia. This work was supported by the Catholic University of Korea, Research Fund, 2008. Corresponding author. Tel.: +82 2 2164 4366. E-mail addresses: [email protected] (J.-H. Park), [email protected] (S.H. Son).",

year = "2009",

month = jun,

day = "28",

doi = "10.1016/j.tcs.2009.02.041",

language = "English",

volume = "410",

pages = "2632--2640",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "27-29",

}

TY - JOUR

T1 - Conditional matching preclusion for hypercube-like interconnection networks

AU - Park, Jung Heum

AU - Son, Sang Hyuk

N1 - Funding Information: This work was done when the first author was visiting Department of Computer Science, University of Virginia. This work was supported by the Catholic University of Korea, Research Fund, 2008. Corresponding author. Tel.: +82 2 2164 4366. E-mail addresses: [email protected] (J.-H. Park), [email protected] (S.H. Son).

PY - 2009/6/28

Y1 - 2009/6/28

N2 - The conditional matching preclusion number of a graph with n vertices is the minimum number of edges whose deletion results in a graph without an isolated vertex that does not have a perfect matching if n is even, or an almost perfect matching if n is odd. We develop some general properties on conditional matching preclusion and then analyze the conditional matching preclusion numbers for some HL-graphs, hypercube-like interconnection networks.

AB - The conditional matching preclusion number of a graph with n vertices is the minimum number of edges whose deletion results in a graph without an isolated vertex that does not have a perfect matching if n is even, or an almost perfect matching if n is odd. We develop some general properties on conditional matching preclusion and then analyze the conditional matching preclusion numbers for some HL-graphs, hypercube-like interconnection networks.

KW - Almost perfect matching

KW - Conditional fault

KW - Edge fault

KW - Fault tolerance

KW - HL-graphs

KW - Perfect matching

KW - Restricted HL-graphs

UR - http://www.scopus.com/inward/record.url?scp=67349204293&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2009.02.041

DO - 10.1016/j.tcs.2009.02.041

M3 - Article

AN - SCOPUS:67349204293

SN - 0304-3975

VL - 410

SP - 2632

EP - 2640

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 27-29

ER -

Conditional matching preclusion for hypercube-like interconnection networks

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this