Packing parameters in graphs: new bounds and a solution to an open problem

DOI10.1007/S10878-019-00410-4MaRDI QIDQ2331585zbMATH OpenOpenAlexWikidataFDO

Authors Doost Ali Mojdeh, B. Samadi

Publication date 29 October 2019

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

Nordhaus-Gaddum inequalityopen packing numberopen problempacking numbertriangle-free graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial optimization (90C27)

Abstract: In this paper, we investigate the packing parameters in graphs. By applying the Mantel's theorem, We give upper bounds on packing and open packing numbers of triangle-free graphs along with characterizing the graphs for which the equalities hold and exhibit sharp Nordhaus-Gaddum type inequalities for packing numbers. We also solve the open problem of characterizing all connected graphs with $h{o}_o(G)=n-omega(G)$ posed in [S. Hamid and S. Saravanakumar, {em Packing parameters in graphs}, Discuss Math. Graph Theory, 35 (2015), 5--16].

Recommendations

• Further results on packing related parameters in graphs
• Packing parameters in graphs
• On open packing number of graphs
• On the packing numbers in graphs
• scientific article; zbMATH DE number 1286740

Cites work

• A survey of Nordhaus-Gaddum type relations
• scientific article; zbMATH DE number 6837043 (Why is no real title available?)
• scientific article; zbMATH DE number 1286740 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Limited packings in graphs
• On open packing number of graphs
• On the \(k\)-limited packing numbers in graphs
• Packing parameters in graphs

Cited in

(4)

• Further results on packing related parameters in graphs
• scientific article; zbMATH DE number 5999574 (Why is no real title available?)
• The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
• More on limited packings in graphs

This page was built for publication: Packing parameters in graphs: new bounds and a solution to an open problem

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