Algebraic approach to fasciagraphs and rotagraphs

被引：39

作者：

Klavzar, S ^{[1
]}

Zerovnik, J ^{[1
]}

机构：

[1] UNIV MARIBOR,FAC TECH SCI,MARIBOR 62000,SLOVENIA

来源：

DISCRETE APPLIED MATHEMATICS | 1996年 / 68卷 / 1-2期

关键词：

D O I：

10.1016/0166-218X(95)00058-Y

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

An algebraic approach is proposed which can be used to solve different problems on fasciagraphs and rotagraphs. A particular instance of this method computes the domination number of fasciagraphs and rotagraphs in O(log n) time, where n is the number of monographs of such a graph. Fasciagraphs and rotagraphs include complete grid graphs P-k square P-n and graphs C-k square C-n. The best previously known algorithms for computing the domination number of P-k square P-n are of lime complexity O(n) (for a fixed k).

引用

页码：93 / 100

页数：8

共 21 条

[1]

[Anonymous], 1986, C NUMER

[2]

[Anonymous], 1979, GRAPHS NETWORKS

[3]

ARNBORG S, 1985, BIT, V25, P2, DOI 10.1007/BF01934985

[4]

ARNBORG S, 1984, TRITANA8404 DEP NUM

[5] THE MATCHING POLYNOMIAL OF A POLYGRAPH [J].

BABIC, D ;

GRAOVAC, A ;

MOHAR, B ;

PISANSKI, T .

DISCRETE APPLIED MATHEMATICS, 1986, 15 (01) :11-24

[6]

CHANG TY, 1994, ARS COMBINATORIA, V38, P97

[7] THE DOMINATION NUMBERS OF THE 5XN AND 6XN GRID GRAPHS [J].

CHANG, TY ;

CLARK, WE .

JOURNAL OF GRAPH THEORY, 1993, 17 (01) :81-107

[8] UNIT DISK GRAPHS [J].

CLARK, BN ;

COLBOURN, CJ ;

JOHNSON, DS .

DISCRETE MATHEMATICS, 1990, 86 (1-3) :165-177

[9]

COCKAYNE EJ, 1985, C NUMER, V47, P217

[10]

FISHER DC, UNPUB J GRAPH THEORY

← 1 2 3 →