On the connectivity of 2-hop neighbor graph

Yun Hou; Jiahu Qin; Changbin Yu

doi:10.1109/CDC.2016.7799205

On the connectivity of 2-hop neighbor graph

Yun Hou, Jiahu Qin, Changbin Yu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The connectivity between different agents is a basic requirement in the control problem of multi-agent systems. For a connected graph, the connectivity corresponding to a 2-hop neighbor graph remains uncertain. In this paper, we consider the problem of verifying the connectivity of 2-hop neighbor graph of a connected graph. The properties of 2-hop neighbor graph from certain basic graphs, such as tree and circle graphs are studied firstly, then arbitrary connected graphs are discussed to investigate the connectivity of the underlying 2-hop neighbor graphs. The necessary and sufficient condition for verifying the connectivity of 2-hop neighbor graphs is proposed. Also a systematic verification strategy is developed, which is able to verify the connectivity of the underlying 2-hop neighbor graph of an arbitrary graph with the computation complexity of O(/V=+/E/), comparing with algebraic solutions.

Original language	English
Title of host publication	2016 IEEE 55th Conference on Decision and Control, CDC 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	6092-6097
Number of pages	6
ISBN (Electronic)	9781509018376
DOIs	https://doi.org/10.1109/CDC.2016.7799205
Publication status	Published - 27 Dec 2016
Event	55th IEEE Conference on Decision and Control, CDC 2016 - Las Vegas, United States Duration: 12 Dec 2016 → 14 Dec 2016

Publication series

Name	2016 IEEE 55th Conference on Decision and Control, CDC 2016

Conference

Conference	55th IEEE Conference on Decision and Control, CDC 2016
Country/Territory	United States
City	Las Vegas
Period	12/12/16 → 14/12/16

Access to Document

10.1109/CDC.2016.7799205

Cite this

@inproceedings{870b463ee2f04f54af6670cc27042b06,

title = "On the connectivity of 2-hop neighbor graph",

abstract = "The connectivity between different agents is a basic requirement in the control problem of multi-agent systems. For a connected graph, the connectivity corresponding to a 2-hop neighbor graph remains uncertain. In this paper, we consider the problem of verifying the connectivity of 2-hop neighbor graph of a connected graph. The properties of 2-hop neighbor graph from certain basic graphs, such as tree and circle graphs are studied firstly, then arbitrary connected graphs are discussed to investigate the connectivity of the underlying 2-hop neighbor graphs. The necessary and sufficient condition for verifying the connectivity of 2-hop neighbor graphs is proposed. Also a systematic verification strategy is developed, which is able to verify the connectivity of the underlying 2-hop neighbor graph of an arbitrary graph with the computation complexity of O(/V=+/E/), comparing with algebraic solutions.",

author = "Yun Hou and Jiahu Qin and Changbin Yu",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 55th IEEE Conference on Decision and Control, CDC 2016 ; Conference date: 12-12-2016 Through 14-12-2016",

year = "2016",

month = dec,

day = "27",

doi = "10.1109/CDC.2016.7799205",

language = "English",

series = "2016 IEEE 55th Conference on Decision and Control, CDC 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "6092--6097",

booktitle = "2016 IEEE 55th Conference on Decision and Control, CDC 2016",

address = "United States",

}

Hou, Y, Qin, J & Yu, C 2016, On the connectivity of 2-hop neighbor graph. in 2016 IEEE 55th Conference on Decision and Control, CDC 2016., 7799205, 2016 IEEE 55th Conference on Decision and Control, CDC 2016, Institute of Electrical and Electronics Engineers Inc., pp. 6092-6097, 55th IEEE Conference on Decision and Control, CDC 2016, Las Vegas, United States, 12/12/16. https://doi.org/10.1109/CDC.2016.7799205

On the connectivity of 2-hop neighbor graph. / Hou, Yun; Qin, Jiahu; Yu, Changbin.
2016 IEEE 55th Conference on Decision and Control, CDC 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 6092-6097 7799205 (2016 IEEE 55th Conference on Decision and Control, CDC 2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the connectivity of 2-hop neighbor graph

AU - Hou, Yun

AU - Qin, Jiahu

AU - Yu, Changbin

PY - 2016/12/27

Y1 - 2016/12/27

N2 - The connectivity between different agents is a basic requirement in the control problem of multi-agent systems. For a connected graph, the connectivity corresponding to a 2-hop neighbor graph remains uncertain. In this paper, we consider the problem of verifying the connectivity of 2-hop neighbor graph of a connected graph. The properties of 2-hop neighbor graph from certain basic graphs, such as tree and circle graphs are studied firstly, then arbitrary connected graphs are discussed to investigate the connectivity of the underlying 2-hop neighbor graphs. The necessary and sufficient condition for verifying the connectivity of 2-hop neighbor graphs is proposed. Also a systematic verification strategy is developed, which is able to verify the connectivity of the underlying 2-hop neighbor graph of an arbitrary graph with the computation complexity of O(/V=+/E/), comparing with algebraic solutions.

AB - The connectivity between different agents is a basic requirement in the control problem of multi-agent systems. For a connected graph, the connectivity corresponding to a 2-hop neighbor graph remains uncertain. In this paper, we consider the problem of verifying the connectivity of 2-hop neighbor graph of a connected graph. The properties of 2-hop neighbor graph from certain basic graphs, such as tree and circle graphs are studied firstly, then arbitrary connected graphs are discussed to investigate the connectivity of the underlying 2-hop neighbor graphs. The necessary and sufficient condition for verifying the connectivity of 2-hop neighbor graphs is proposed. Also a systematic verification strategy is developed, which is able to verify the connectivity of the underlying 2-hop neighbor graph of an arbitrary graph with the computation complexity of O(/V=+/E/), comparing with algebraic solutions.

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

U2 - 10.1109/CDC.2016.7799205

DO - 10.1109/CDC.2016.7799205

M3 - Conference contribution

T3 - 2016 IEEE 55th Conference on Decision and Control, CDC 2016

SP - 6092

EP - 6097

BT - 2016 IEEE 55th Conference on Decision and Control, CDC 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 55th IEEE Conference on Decision and Control, CDC 2016

Y2 - 12 December 2016 through 14 December 2016

ER -

On the connectivity of 2-hop neighbor graph

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this