Linear polynomial-time algorithms to construct 4-connected 4-regular locally connected claw-free graphs

Ming Chu Li; Liming Xiong; Hong Liu

Linear polynomial-time algorithms to construct 4-connected 4-regular locally connected claw-free graphs

Ming Chu Li^*, Liming Xiong, Hong Liu

^*Corresponding author for this work

School of Mathematics and Statistics

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

Abstract

A vertex of a graph is locally connected if its neighborhood is connected. A graph G is locally connected if every vertex of G is locally connected. A graph is called claw-free if it does not contain a copy of K_1,3 as an induced subgraph. In this paper, we provide a constructive characterization of 4-connected 4-regular locally connected claw-free graphs. From its proof, we can give a linear polynomial-time algorithm to construct a 4-connected 4-regular locally connected claw-free graph.

Original language	English
Title of host publication	Computational Science - ICCS 2007 - 7th International Conference, Proceedings
Pages	329-333
Number of pages	5
Edition	PART 3
Publication status	Published - 2007
Event	7th International Conference on Computational Science, ICCS 2007 - Beijing, China Duration: 27 May 2007 → 30 May 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 3
Volume	4489 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Conference on Computational Science, ICCS 2007
Country/Territory	China
City	Beijing
Period	27/05/07 → 30/05/07

Keywords

Claw-free graph
Constructive characterization
Linear polynomial-time

Cite this

Li, M. C., Xiong, L., & Liu, H. (2007). Linear polynomial-time algorithms to construct 4-connected 4-regular locally connected claw-free graphs. In Computational Science - ICCS 2007 - 7th International Conference, Proceedings (PART 3 ed., pp. 329-333). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4489 LNCS, No. PART 3).

Li, Ming Chu ; Xiong, Liming ; Liu, Hong. / Linear polynomial-time algorithms to construct 4-connected 4-regular locally connected claw-free graphs. Computational Science - ICCS 2007 - 7th International Conference, Proceedings. PART 3. ed. 2007. pp. 329-333 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 3).

@inproceedings{3c01f753ecf44c0c94d8e0efc1ac3071,

title = "Linear polynomial-time algorithms to construct 4-connected 4-regular locally connected claw-free graphs",

abstract = "A vertex of a graph is locally connected if its neighborhood is connected. A graph G is locally connected if every vertex of G is locally connected. A graph is called claw-free if it does not contain a copy of K1,3 as an induced subgraph. In this paper, we provide a constructive characterization of 4-connected 4-regular locally connected claw-free graphs. From its proof, we can give a linear polynomial-time algorithm to construct a 4-connected 4-regular locally connected claw-free graph.",

keywords = "Claw-free graph, Constructive characterization, Linear polynomial-time",

author = "Li, {Ming Chu} and Liming Xiong and Hong Liu",

year = "2007",

language = "English",

isbn = "9783540725879",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 3",

pages = "329--333",

booktitle = "Computational Science - ICCS 2007 - 7th International Conference, Proceedings",

edition = "PART 3",

note = "7th International Conference on Computational Science, ICCS 2007 ; Conference date: 27-05-2007 Through 30-05-2007",

}

Li, MC, Xiong, L & Liu, H 2007, Linear polynomial-time algorithms to construct 4-connected 4-regular locally connected claw-free graphs. in Computational Science - ICCS 2007 - 7th International Conference, Proceedings. PART 3 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 3, vol. 4489 LNCS, pp. 329-333, 7th International Conference on Computational Science, ICCS 2007, Beijing, China, 27/05/07.

Linear polynomial-time algorithms to construct 4-connected 4-regular locally connected claw-free graphs. / Li, Ming Chu; Xiong, Liming; Liu, Hong.
Computational Science - ICCS 2007 - 7th International Conference, Proceedings. PART 3. ed. 2007. p. 329-333 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4489 LNCS, No. PART 3).

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

TY - GEN

T1 - Linear polynomial-time algorithms to construct 4-connected 4-regular locally connected claw-free graphs

AU - Li, Ming Chu

AU - Xiong, Liming

AU - Liu, Hong

PY - 2007

Y1 - 2007

N2 - A vertex of a graph is locally connected if its neighborhood is connected. A graph G is locally connected if every vertex of G is locally connected. A graph is called claw-free if it does not contain a copy of K1,3 as an induced subgraph. In this paper, we provide a constructive characterization of 4-connected 4-regular locally connected claw-free graphs. From its proof, we can give a linear polynomial-time algorithm to construct a 4-connected 4-regular locally connected claw-free graph.

AB - A vertex of a graph is locally connected if its neighborhood is connected. A graph G is locally connected if every vertex of G is locally connected. A graph is called claw-free if it does not contain a copy of K1,3 as an induced subgraph. In this paper, we provide a constructive characterization of 4-connected 4-regular locally connected claw-free graphs. From its proof, we can give a linear polynomial-time algorithm to construct a 4-connected 4-regular locally connected claw-free graph.

KW - Claw-free graph

KW - Constructive characterization

KW - Linear polynomial-time

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

M3 - Conference contribution

AN - SCOPUS:38149083521

SN - 9783540725879

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 329

EP - 333

BT - Computational Science - ICCS 2007 - 7th International Conference, Proceedings

T2 - 7th International Conference on Computational Science, ICCS 2007

Y2 - 27 May 2007 through 30 May 2007

ER -

Li MC, Xiong L, Liu H. Linear polynomial-time algorithms to construct 4-connected 4-regular locally connected claw-free graphs. In Computational Science - ICCS 2007 - 7th International Conference, Proceedings. PART 3 ed. 2007. p. 329-333. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 3).

Linear polynomial-time algorithms to construct 4-connected 4-regular locally connected claw-free graphs

Abstract

Publication series

Conference

Keywords

Other files and links

Fingerprint

Cite this