Cycles in partially square graphs

被引:1
作者
Ainouche, A
Kouider, M
机构
[1] Univ Antilles & Guyane, CEREGMIA, F-97275 Schoelcher, France
[2] Univ Paris Sud, LRI, URA 410 CNRS, F-91405 Orsay, France
关键词
Simple Graph; Stability Number; Undirected Simple Graph;
D O I
10.1007/PL00007232
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In this work we consider finite undirected simple graphs. If C = (V, E) is a graph we denote by alpha (G) the stability number of G. For any vertex v let N[x] be the union of x and the neighborhood N(x). For each pair of vertices a b of G we associate the set J(a, b) as follows. J(a, b) = {u is an element of N[a] boolean AND N[b] \ N(u) subset of or equal to N[a] boolean OR N[b]). Given a graph G. its partially square G* is the graph obtained by adding an edge uv for each pair It, v of vertices of G at distance 2 whenever J(u, 2,) is not empty. In the case G is a claw-free graph, G* is equal to If G is k-connected, we cover the vertices of G by at most [alpha (G*)/k] cycles, where alpha (G*) is the stability number of the partially square graph of G. On the other hand we consider in G* conditions on the sum of the degrees. Let G be any 2-connected graph and t be any integer (t greater than or equal to 2). If Sigma (x is an element ofS) deg(G)(x) greater than or equal to1 \G\, for every t-stable set S subset of or equal to V(G) of G* then the vertex set of G can be covered with t-1 cycles. Different corollaries on covering by paths are given.
引用
收藏
页码:1 / 9
页数:9
相关论文
共 5 条
[1]  
AINOUCHE A, 1990, ARS COMBINATORIA, V29C, P110
[2]   Hamiltonism and partially square graphs [J].
Ainouche, A ;
Kouider, M .
GRAPHS AND COMBINATORICS, 1999, 15 (03) :257-265
[3]  
Chvatal V., 1972, DISCRETE MATH, V2, P111, DOI DOI 10.1016/0012-365X(72)90079-9
[4]   Covering cycles and k-term degree sums [J].
Kouider, M ;
Long, Z .
COMBINATORICA, 1996, 16 (03) :407-412