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 -