Packing 3-vertex paths in claw-free graphs and related topics

被引:27
作者
Kelmans, Alexander [1 ,2 ]
机构
[1] Univ Puerto Rico, San Juan, PR 00936 USA
[2] Rutgers State Univ, New Brunswick, NJ 08903 USA
关键词
Claw-free graph; Cubic graph; Vertex disjoint packing; Edge disjoint packing; P-3-factor; P-3-packing; Path-factor; Induced packing; Graph domination; Graph minor; The Hadwiger conjecture;
D O I
10.1016/j.dam.2010.05.001
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A A-factor of a graph G is a spanning subgraph of G whose every component is a 3-vertex path. Let v(G) be the number of vertices of G and gamma(G) the domination number of G. A claw is a graph with four vertices and three edges incident to the same vertex. A graph is claw-free if it does not have an induced subgraph isomorphic to a claw. Our results include the following. Let G be a 3-connected claw-free graph, x epsilon V(C), e = xy epsilon E(G), and L a 3-vertex path in G. Then (a1) if v(G) 0 mod 3, then G has a A-factor containing (avoiding) e, (a2) if v(G) 1 mod 3, then G - x has a A-factor, (a3) if v(G) 2 mod 3, then G - {x, y} has a A-factor, (a4) if v(G) 0 mod 3 and G is either cubic or 4-connected, then G - L has a A-factor, (a5) if G is cubic with v(G) >= 6 and E is a set of three edges in G, then G - E has a A-factor if and only if the subgraph induced by E in G is not a claw and not a triangle, (a6) if v(G) 1 mod 3, then G - {v, e} has a A-factor for every vertex v and every edge e in G, (a7) if v(G) 1 mod 3, then there exist a 4-vertex path Pi and a claw Y in G such that G-Pi and G-Y have A-factors, and (a8)y(G) <= (inverted right perpendicular) v(G)/3(inverted left perpendicular) and if in addition G is not a cycle and v(G) 1 mod 3, then gamma(G) <= (left perpendicular)v(G)/ 3(right perpendicular). We also explore the relations between packing problems of a graph and its line graph to obtain some results on different types of packings and discuss relations between A-packing and domination problems. Published by Elsevier B.V.
引用
收藏
页码:112 / 127
页数:16
相关论文
共 24 条