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

DOI10.1016/J.DAM.2010.05.001zbMATH Open1206.05058arXiv0910.4681OpenAlexW2072174759MaRDI QIDQ617645FDOQ617645

Authors: Alexander Kelmans 

Publication date: 21 January 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: An L-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 d(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 has no induced subgraph isomorphic to a claw. Our results include the following. Let G be a 3-connected claw-free graph, x a vertex in G, e = xy an edge in G, and P a 3-vertex path in G. Then (a1) if v(G) = 0 mod 3, then G has an L-factor containing (avoiding) e, (a2) if v(G) = 1 mod 3, then G - x has an L-factor, (a3) if v(G) = 2 mod 3, then G - {x,y} has an L-factor, (a4) if v(G) = 0 mod 3 and G is either cubic or 4-connected, then G - P has an L-factor, (a5) if G is cubic with v(G) > 5 and E is a set of three edges in G, then G - E has an L-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 an L-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 N and a claw Y in G such that G - N and G - Y have L-factors, and (a8) d(G) < v(G)/3 +1 and if in addition G is not a cycle and v(G) = 1 mod 3, then d(G) < v(G)/3. We explore the relations between packing problems of a graph and its line graph to obtain some results on different types of packings. We also discuss relations between L-packing and domination problems as well as between induced L-packings and the Hadwiger conjecture. Keywords: claw-free graph, cubic graph, vertex disjoint packing, edge disjoint packing, 3-vertex factor, 3-vertex packing, path-factor, induced packing, graph domination, graph minor, the Hadwiger conjecture.

Full work available at URL: https://arxiv.org/abs/0910.4681

Recommendations

• On packing 3-vertex paths in a graph
• A note on path factors in claw-free graphs.
• On maximum \(P_3\)-packing in claw-free subcubic graphs
• On the connectivity and matchings in 3-vertex-critical claw-free graphs
• Path factors in claw-free graphs

zbMATH Keywords

graph dominationclaw-free graphcubic graphgraph minor\(P_{3}\)-factor\(P_{3}\)-packingedge disjoint packinginduced packingpath-factorthe Hadwiger conjecturevertex disjoint packing

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Cites Work

• Graph theory
• Matching theory
• Optimal packing of induced stars in a graph
• Hamiltonian results inK1,3-free graphs
• Paths, Stars and the Number Three
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• On domination in connected cubic graphs
• How many disjoint 2-edge paths must a cubic graph have?
• A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
• Efficient subgraphs packing
• On packing 3-vertex paths in a graph
• Packingk-edge trees in graphs of restricted vertex degrees
• Packings by Complete Bipartite Graphs
• Asymptotically optimal tree-packings in regular graphs

Cited In (18)

• Path-factor critical covered graphs and path-factor uniform graphs
• The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices
• Some existence theorems on path factors with given properties in graphs
• Component factors and binding number conditions in graphs
• On maximum \(P_3\)-packing in claw-free subcubic graphs
• Some results on path-factor critical avoidable graphs
• Some results about ID-path-factor critical graphs
• A \(5k\)-vertex kernel for \(P_2\)-packing
• Independence number and minimum degree for path-factor critical uniform graphs
• Some results about star-factors in graphs
• The maximum 3-star packing problem in claw-free cubic graphs
• Characterizing spanning trees via the size or the spectral radius of graphs
• Toughness, isolated toughness and path factors in graphs
• On path-factor critical uniform graphs
• On path-factor critical deleted (or covered) graphs
• Block allocation of a sequential resource
• On packing 3-vertex paths in a graph
• Path factors in subgraphs

This page was built for publication: Packing 3-vertex paths in claw-free graphs and related topics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q617645)