Scattering number and modular decomposition

被引:4
作者
Giakoumakis, V
Roussel, F
Thuillier, H
机构
[1] UNIV PICARDIE,LARIA,F-80000 AMIENS,FRANCE
[2] UNIV ORLEANS,LIFO,F-45067 ORLEANS 2,FRANCE
关键词
D O I
10.1016/S0012-365X(96)00180-X
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The scattering number of a graph G equals max{c(G\S) - \S\ S is a cutset of G} where c(G\S) denotes the number of connected components in G\S. Jung (1978) has given for any graph having no induced path on four vertices (P-4-free graph) a correspondence between the value of its scattering number and the existence of Hamiltonian paths or Hamiltonian cycles, Hochstattler and Tinhofer (to appear) studied the Hamiltonicity of P-4-sparse graphs introduced by Hoang (1985). In this paper, using modular decomposition, we show that the results of Jung and Hochstattler and Tinhofer can be generalized to a subclass of the family of semi-P-4-sparse graphs introduced in Fouquet and Giakoumakis (to appear).
引用
收藏
页码:321 / 342
页数:22
相关论文
共 24 条
[1]   A FAST ALGORITHM FOR THE DECOMPOSITION OF GRAPHS AND POSETS [J].
BUER, H ;
MOHRING, RH .
MATHEMATICS OF OPERATIONS RESEARCH, 1983, 8 (02) :170-184
[2]  
Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6
[3]   COMPLEMENT REDUCIBLE GRAPHS [J].
CORNEIL, DG ;
LERCHS, H ;
BURLINGHAM, LS .
DISCRETE APPLIED MATHEMATICS, 1981, 3 (03) :163-174
[4]   A LINEAR RECOGNITION ALGORITHM FOR COGRAPHS [J].
CORNEIL, DG ;
PERL, Y ;
STEWART, LK .
SIAM JOURNAL ON COMPUTING, 1985, 14 (04) :926-934
[5]  
Cournier A., 1994, LECT NOTES COMPUTER, V787, P68
[6]  
FOUQUET JL, IN PRESS DISCRETE MA
[7]   TRANSITIV ORIENTIERBARE GRAPHEN [J].
GALLAI, T .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1967, 18 (1-2) :25-&
[8]  
GIAKOUMAKIS V, 1996, SCATTERING NUMBER HA
[9]  
GIAKOUMAKIS V, 1995, 4 TW WORKSH GRAPHS C
[10]  
Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs