Independence number in path graphs

被引：0

作者：

Knor, M

Niepel, L

机构：

[1] Slovak Univ Technol Bratislava, Fac Civil Engn, Dept Math, Bratislava 81368, Slovakia

[2] Kuwait Univ, Fac Sci, Dept Math & Comp Sci, Safat 13060, Kuwait

来源：

COMPUTING AND INFORMATICS | 2004年 / 23卷 / 02期

关键词：

path graph; independence number; iterated line graph; graph dynamics; (non)deterministic algorithm;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In the paper we present results, which allow us to compute the independence numbers of P-2-path graphs and P-3-path graphs of special graphs. As P-2(G) and P-3(G) are subgraphs of iterated line graphs L-2(G) and L-3(G), respectively, we compare our results with the independence numbers of corresponding iterated line graphs.

引用

页码：179 / 187

页数：9

共 17 条

[1]

Aldred REL, 1997, J GRAPH THEOR, V26, P35, DOI 10.1002/(SICI)1097-0118(199709)26:1<35::AID-JGT5>3.0.CO

[2]

2-I

[3]

[Anonymous], 1957, Casopis Pest Mat

[4]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[5] Edge-connectivity and super edge-connectivity of P2-path graphs [J].

Balbuena, C ;

Ferrero, D .

DISCRETE MATHEMATICS, 2003, 269 (1-3) :13-20

[6]

Belan A., 1999, ACTA MATH U COMENIAN, VLXVIII, P111

[7] PATH GRAPHS [J].

BROERSMA, HJ ;

HOEDE, C .

JOURNAL OF GRAPH THEORY, 1989, 13 (04) :427-444

[8]

Ferrero D., 2003, ACTA MATH U COMEN, V72, P59

[9] Diameter in iterated path graphs [J].

Knor, M ;

Niepel, L .

DISCRETE MATHEMATICS, 2001, 233 (1-3) :151-161

[10]

Knor M., 2002, AUSTR J COMB, V25, P175

← 1 2 →