On maximum $$P_3$$ -packing in claw-free subcubic graphs
Tóm tắt
Let
$$P_3$$
denote the path on three vertices. A
$$P_3$$
-packing of a given graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is isomorphic to
$$P_3$$
. The maximum
$$P_3$$
-packing problem is to find a
$$P_3$$
-packing of a given graph G which contains the maximum number of vertices of G. The perfect
$$P_3$$
-packing problem is to decide whether a graph G has a
$$P_3$$
-packing that covers all vertices of G. Kelmans (Discrete Appl Math 159:112–127, 2011) proposed the following problem: Is the
$$P_3$$
-packing problem NP-hard in the class of claw-free graphs? In this paper, we solve the problem by proving that the perfect
$$P_3$$
-packing problem in claw-free cubic planar graphs is NP-complete. In addition, we show that for any connected claw-free cubic graph (resp. (2, 3)-regular graph, subcubic graph) G with
$$v(G)\ge 14$$
(resp.
$$v(G)\ge 8$$
,
$$v(G)\ge 3$$
), the maximum
$$P_3$$
-packing of G covers at least
$$\lceil \frac{9v(G)-6}{10} \rceil $$
(resp.
$$\lceil \frac{6v(G)-6}{7} \rceil $$
,
$$\lceil \frac{3v(G)-6}{4} \rceil $$
) vertices, where v(G) denotes the order of G, and the bound is sharp. The proofs imply polynomial-time algorithms.
Tài liệu tham khảo
Akiyama J, Kano M (1985) Factors and factorizations of graphs—a survey. J Graph Theory 9:1–42
Chang M-S, Chen L-H, Hung L-J (2016) An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs. J Combin Optim 32:594–607
Chang M-S, Chen L-H, Hung L-J (2014) A \(5k\) kernel for \(P_2\)-packing in net-free graphs. In: Proceedings of ICSEC, pp 12–17
Dyer ME, Frieze AM (1986) Planar 3DM is NP-Complete. J Algorithms 7(2):174–184
Feng Q, Wang J, Chen J (2014) Matching and weighted \(P_2\)-packing: algorithms and kernels. Theor Comput Sci 522:85–94
Feng Q, Wang J, Li S, Chen J (2015) Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems. J Combin Optim 19:125–140
Fernau H, Raible D (2009) A parameterized perspective on packing paths of length two. J Combin Optim 18:319–341
Hell P, Kirkpatrick DG (1984) Packing by cliques and by finite families of graphs. Discrete Math 49(1):45–59
Hell P, Kirkpatrick DG (1986) Packing by complete bipartite graphs. SIAM J Algebraic Discrete Methods 7(2):199–209
Hurkens C, Schrijver A (1989) On the size of systems of sets every \(t\) of which have an SDR, with application to worst case ratio of heuristics for packing problem. SIAM J Discrete Math 2(1):68–72
Kaneko A, Kelmans A, Nishimura T (2001) On packing \(3\)-vertex paths in a graph. J Graph Theory 36:175–197
Kelamns A, Mubayi D (2003) How many disjoint \(2\)-edge paths must a cubic graph have? J Graph Theory 45(1):57–79
Kelmans AK (2007) Packing \(k\)-edge trees in graphs of restricted vertex degree. J Graph Theory 55(4):306–323
Kelmans A (2011) Packing \(3\)-vertex paths in claw-free graphs and related topics. Discrete Appl Math 159:112–127
Kirkpatrick DG, Hell P (1983) On the complexity of general graph factor problems. SIAM J Comput 12(3):601–609
Kosowski A, Malafiejski M, Żyliński P (2005) Packing three-vertex paths in a subcubic graph. In: 2005 European conference on combinatorics, graph theory and applications (EuroComb’05), Berlin, pp 213–218. hal-01184370
Kosowski A, Malafiejski M, Żyliński P (2008) Tighter bounds on the size of a maximum \(P_3\)-matching in a cubic graph. Graphs Combin 24:461–468
Kosowski A, Żyliński P (2008) Packing three-vertex paths in \(2\)-connected cubic graphs. Ars Combin 89:95–113
Kosowski A, Malafiejski M, Żyliński P (2006) Parallel processing subsystems with redundancy in a distributed environment. LNCS 3911:1002–1009
Monnot J, Toulouse S (2007) The path partition problem and related problems in bipartite graphs. Oper Res Lett 35:677–684
Neggazi B, Turau V, Haddad M (2015) A self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs. Inf Process Lett 115(11):892–898
Prieto E, Sloper C (2006) Looking at the stars. Theor Comput Sci 351(3):437–445
Wang J, Ning D, Feng Q, Chen J (2010) An improved kernelization for \(P_2\)-packing. Inf Process Lett 110:188–192