On the g-good-neighbor connectivity of graphs

Zhao Wang; Yaping Mao; Sun Yuan Hsieh; Jichang Wu

doi:10.1016/j.tcs.2019.11.021

On the g-good-neighbor connectivity of graphs

Zhao Wang, Yaping Mao, Sun Yuan Hsieh, Jichang Wu

Department of Computer Science and Information Engineering

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

1 Citation (Scopus)

Abstract

Connectivity and diagnosability are two important parameters for the fault tolerant of an interconnection network G. In 1996, Fàbrega and Fiol proposed the g-good-neighbor connectivity of G. In this paper, we show that 1≤κ^g(G)≤n−2g−2 for [Formula presented], and graphs with κ^g(G)=1,2 and trees with κ^g(T_n)=n−t for [Formula presented] are characterized, respectively. In the end, we get the three extremal results for the g-good-neighbor connectivity.

Original language	English
Pages (from-to)	139-148
Number of pages	10
Journal	Theoretical Computer Science
Volume	804
DOIs	https://doi.org/10.1016/j.tcs.2019.11.021
Publication status	Published - 2020 Jan 12

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1016/j.tcs.2019.11.021

Fingerprint Dive into the research topics of 'On the g-good-neighbor connectivity of graphs'. Together they form a unique fingerprint.

Cite this

@article{f60333707e13447da620f46f1f6706ab,

title = "On the g-good-neighbor connectivity of graphs",

abstract = "Connectivity and diagnosability are two important parameters for the fault tolerant of an interconnection network G. In 1996, F{\`a}brega and Fiol proposed the g-good-neighbor connectivity of G. In this paper, we show that 1≤κg(G)≤n−2g−2 for [Formula presented], and graphs with κg(G)=1,2 and trees with κg(Tn)=n−t for [Formula presented] are characterized, respectively. In the end, we get the three extremal results for the g-good-neighbor connectivity.",

author = "Zhao Wang and Yaping Mao and Hsieh, {Sun Yuan} and Jichang Wu",

note = "Funding Information: Supported by the National Science Foundation of China (Nos. 11601254, 11551001, 11161037, 61763041, 11661068, and 11461054) and the Science Found of Qinghai Province (Nos. and 2014-ZJ-907) and the Qinghai Key Laboratory of Internet of Things Project (2017-ZJ-Y21).",

year = "2020",

month = jan,

day = "12",

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

language = "English",

volume = "804",

pages = "139--148",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - On the g-good-neighbor connectivity of graphs

AU - Wang, Zhao

AU - Mao, Yaping

AU - Hsieh, Sun Yuan

AU - Wu, Jichang

N1 - Funding Information: Supported by the National Science Foundation of China (Nos. 11601254, 11551001, 11161037, 61763041, 11661068, and 11461054) and the Science Found of Qinghai Province (Nos. and 2014-ZJ-907) and the Qinghai Key Laboratory of Internet of Things Project (2017-ZJ-Y21).

PY - 2020/1/12

Y1 - 2020/1/12

N2 - Connectivity and diagnosability are two important parameters for the fault tolerant of an interconnection network G. In 1996, Fàbrega and Fiol proposed the g-good-neighbor connectivity of G. In this paper, we show that 1≤κg(G)≤n−2g−2 for [Formula presented], and graphs with κg(G)=1,2 and trees with κg(Tn)=n−t for [Formula presented] are characterized, respectively. In the end, we get the three extremal results for the g-good-neighbor connectivity.

AB - Connectivity and diagnosability are two important parameters for the fault tolerant of an interconnection network G. In 1996, Fàbrega and Fiol proposed the g-good-neighbor connectivity of G. In this paper, we show that 1≤κg(G)≤n−2g−2 for [Formula presented], and graphs with κg(G)=1,2 and trees with κg(Tn)=n−t for [Formula presented] are characterized, respectively. In the end, we get the three extremal results for the g-good-neighbor connectivity.

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

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

U2 - 10.1016/j.tcs.2019.11.021

DO - 10.1016/j.tcs.2019.11.021

M3 - Article

AN - SCOPUS:85076213687

VL - 804

SP - 139

EP - 148

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -