Conditional Fault Hamiltonicity of the Star Graph

Cheng-Kuan Lin; Jiann-Mean Tan; Lih Hsing Hsu; Eddie Cheng; Liptak Laszlo

Conditional Fault Hamiltonicity of the Star Graph

Cheng-Kuan Lin, Jiann-Mean Tan, Lih Hsing Hsu^*, Eddie Cheng, Liptak Laszlo

^*Corresponding author for this work

Department of Computer Science

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

1 Scopus citations

Abstract

Fault tolerance is an important property on network performance. A graph G is k-edge-fault conditional hamiltonian if G - F is hamiltonian for every F subset of E(G) with vertical bar F vertical bar <= k and delta(G - F) >= 2. In this paper we show that for n >= 4 the n-dimensional star graph S-n is (3n - 10)-edge-fault conditional hamiltonian.

Original language	English
Pages (from-to)	111-127
Journal	Ars Combinatoria
Volume	113
State	Published - Jan 2014

Keywords

hamiltonian; star graphs; fault-tolerant

Fingerprint Dive into the research topics of 'Conditional Fault Hamiltonicity of the Star Graph'. Together they form a unique fingerprint.

Cite this

@article{f4e056d13ef04fd9944e6d4b09364e27,

title = "Conditional Fault Hamiltonicity of the Star Graph",

abstract = "Fault tolerance is an important property on network performance. A graph G is k-edge-fault conditional hamiltonian if G - F is hamiltonian for every F subset of E(G) with vertical bar F vertical bar <= k and delta(G - F) >= 2. In this paper we show that for n >= 4 the n-dimensional star graph S-n is (3n - 10)-edge-fault conditional hamiltonian.",

keywords = "hamiltonian; star graphs; fault-tolerant",

author = "Cheng-Kuan Lin and Jiann-Mean Tan and Hsu, {Lih Hsing} and Eddie Cheng and Liptak Laszlo",

year = "2014",

month = jan,

language = "English",

volume = "113",

pages = "111--127",

journal = "Ars Combinatoria",

issn = "0381-7032",

publisher = "Charles Babbage Research Centre",

}

TY - JOUR

T1 - Conditional Fault Hamiltonicity of the Star Graph

AU - Lin, Cheng-Kuan

AU - Tan, Jiann-Mean

AU - Hsu, Lih Hsing

AU - Cheng, Eddie

AU - Laszlo, Liptak

PY - 2014/1

Y1 - 2014/1

N2 - Fault tolerance is an important property on network performance. A graph G is k-edge-fault conditional hamiltonian if G - F is hamiltonian for every F subset of E(G) with vertical bar F vertical bar <= k and delta(G - F) >= 2. In this paper we show that for n >= 4 the n-dimensional star graph S-n is (3n - 10)-edge-fault conditional hamiltonian.

AB - Fault tolerance is an important property on network performance. A graph G is k-edge-fault conditional hamiltonian if G - F is hamiltonian for every F subset of E(G) with vertical bar F vertical bar <= k and delta(G - F) >= 2. In this paper we show that for n >= 4 the n-dimensional star graph S-n is (3n - 10)-edge-fault conditional hamiltonian.

KW - hamiltonian; star graphs; fault-tolerant

M3 - Article

VL - 113

SP - 111

EP - 127

JO - Ars Combinatoria

JF - Ars Combinatoria

SN - 0381-7032

ER -