The maximum 3-star packing problem in claw-free cubic graphs

Wenying Xi and Wensong Lin ()
Additional contact information
Wenying Xi: Southeast University
Wensong Lin: Southeast University

Journal of Combinatorial Optimization, 2024, vol. 47, issue 5, No 3, 16 pages

Abstract: Abstract A 3-star is a complete bipartite graph $$K_{1,3}$$ K 1 , 3 . A 3-star packing of a graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is a 3-star. The maximum 3-star packing problem is to find a 3-star packing of a given graph with the maximum number of 3-stars. A 2-independent set of a graph G is a subset S of V(G) such that for each pair of vertices $$u,v\in S$$ u , v ∈ S , paths between u and v are all of length at least 3. In cubic graphs, the maximum 3-star packing problem is equivalent to the maximum 2-independent set problem. The maximum 2-independent set problem was proved to be NP-hard on cubic graphs (Kong and Zhao in Congressus Numerantium 143:65–80, 2000), and the best approximation algorithm of maximum 2-independent set problem for cubic graphs has approximation ratio $$\frac{8}{15}$$ 8 15 (Miyano et al. in WALCOM 2017, Proceedings, pp 228–240). In this paper, we first prove that the maximum 3-star packing problem is NP-hard in claw-free cubic graphs and then design a linear-time algorithm which can find a 3-star packing of a connected claw-free cubic graph G covering at least $$\frac{3v(G)-8}{4}$$ 3 v ( G ) - 8 4 vertices, where v(G) denotes the number of vertices of G.

Keywords: Cubic graphs; Claw-free graphs; 3-Star packing; Approximation algorithm (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01115-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:5:d:10.1007_s10878-024-01115-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01115-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().