The packing number of cubic graphs

Wayne Goddard; Michael A. Henning

doi:10.1016/j.disopt.2024.100850

The packing number of cubic graphs

Wayne Goddard, Michael A. Henning

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

A packing in a graph is a set of vertices that are mutually distance at least 3 apart. By using optimization and linear programming to help analyze the greedy algorithm, we improve on a result of Favaron and show that every connected cubic graph of order n has a packing of size at least [Formula presented].

Original language	English
Article number	100850
Journal	Discrete Optimization
Volume	53
DOIs	https://doi.org/10.1016/j.disopt.2024.100850
Publication status	Published - Aug 2024

Keywords

Bounds
Cubic graph
Optimization
Packing

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/j.disopt.2024.100850

Cite this

@article{09555bc1a9924c68b921bb044031ed37,

title = "The packing number of cubic graphs",

abstract = "A packing in a graph is a set of vertices that are mutually distance at least 3 apart. By using optimization and linear programming to help analyze the greedy algorithm, we improve on a result of Favaron and show that every connected cubic graph of order n has a packing of size at least [Formula presented].",

keywords = "Bounds, Cubic graph, Optimization, Packing",

author = "Wayne Goddard and Henning, {Michael A.}",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier B.V.",

year = "2024",

month = aug,

doi = "10.1016/j.disopt.2024.100850",

language = "English",

volume = "53",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - The packing number of cubic graphs

AU - Goddard, Wayne

AU - Henning, Michael A.

PY - 2024/8

Y1 - 2024/8

N2 - A packing in a graph is a set of vertices that are mutually distance at least 3 apart. By using optimization and linear programming to help analyze the greedy algorithm, we improve on a result of Favaron and show that every connected cubic graph of order n has a packing of size at least [Formula presented].

AB - A packing in a graph is a set of vertices that are mutually distance at least 3 apart. By using optimization and linear programming to help analyze the greedy algorithm, we improve on a result of Favaron and show that every connected cubic graph of order n has a packing of size at least [Formula presented].

KW - Bounds

KW - Cubic graph

KW - Optimization

KW - Packing

UR - http://www.scopus.com/inward/record.url?scp=85200009659&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2024.100850

DO - 10.1016/j.disopt.2024.100850

M3 - Article

AN - SCOPUS:85200009659

SN - 1572-5286

VL - 53

JO - Discrete Optimization

JF - Discrete Optimization

M1 - 100850

ER -

The packing number of cubic graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this