Near packings with restriction on degrees in graphs

Qian Yang and Yunshu Gao

Applied Mathematics and Computation, 2024, vol. 477, issue C

Abstract: In graph theory, a packing within graph G is defined as a collection H={H1,H2}, where H1 and H2 are both equivalent to G, yet they exist as edge-disjoint subgraphs within Kn. Considering a positive integer k, we introduce Dk, a set comprising graphs within G, each with a maximum degree not exceeding k. Extending the concept of a packing, a near packing that accommodates Dk in graph G emerges, realized by overlapping two iterations of G. In this configuration, the intersecting subgraph formed by edges shared in both G copies is a member of Dk. The notation m(n,Dk) represents the highest possible value of m, ensuring each graph with order n and size at most m can incorporate a near packing that accommodates Dk. A notable case is m(n,D0)=n−2, highlighting that a near packing which admits D0 equates to a standard packing. This paper focuses on establishing the value of m(n,D1)=⌊3n−52⌋.

Keywords: Packing; Near packing; Extremal problem (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300324002893
Full text for ScienceDirect subscribers only

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:eee:apmaco:v:477:y:2024:i:c:s0096300324002893

DOI: 10.1016/j.amc.2024.128828

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().