Universal maximal packing functions of graphs

DOI10.1016/0012-365X(95)00097-GMaRDI QIDQ1126177zbMATH OpenFDO

Authors E. J. Cockayne, Odile Favaron, Christina M. Mynhardt

Publication date 8 December 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00097-G

zbMATH Keywords

packing function

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

A nonnegative function \(f\) defined on the vertex set of a graph \(G\) is a packing function (PF) if for each vertex \(v\) the sum of the values of \(f\) over the closed neighbourhood of \(v\) is at most 1; such a function \(f\) is a maximal packing function (MPF) if it no longer satisfies the definition of a PF when its value is increased for any vertex. The authors consider the existence of MPFs with the property that their convex combinations with all other MPFs are themselves MPFs.

Recommendations

• NP-completeness of the \(\{k \}\)-packing function problem in graphs
• $$\{k\}$$-Packing Functions of Graphs
• On the complexity of the {\(k\)}-packing function problem
• Graphs with unique maximum packing of closed neighborhoods
• Towards a polynomial equivalence between \(\{k\}\)-packing functions and \(k\)-limited packings in graphs

Cites work

• scientific article; zbMATH DE number 4130427 (Why is no real title available?)
• scientific article; zbMATH DE number 4130428 (Why is no real title available?)
• scientific article; zbMATH DE number 30748 (Why is no real title available?)
• scientific article; zbMATH DE number 1043893 (Why is no real title available?)
• scientific article; zbMATH DE number 812078 (Why is no real title available?)
• scientific article; zbMATH DE number 844153 (Why is no real title available?)
• scientific article; zbMATH DE number 867701 (Why is no real title available?)
• scientific article; zbMATH DE number 975353 (Why is no real title available?)
• scientific article; zbMATH DE number 3211481 (Why is no real title available?)
• Matching theory
• On the Fractional Covering Number of Hypergraphs
• Relations between packing and covering numbers of a tree
• Total dominating functions in trees: Minimality and convexity

Cited in

(1)

• Weakly union-free maximum packings

This page was built for publication: Universal maximal packing functions of graphs

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