Loading...
research article
Minimal graphs for 2-factor extension
August 15, 2020
Let G = (V, E) be a simple loopless finite undirected graph. We say that G is (2-factor) expandable if for any non-edge uv, G + uv has a 2-factor F that contains uv. We are interested in the following: Given a positive integer n = vertical bar V vertical bar, what is the minimum cardinality of E such that there exists G = (V, E) which is 2-factor expandable? This minimum number is denoted by Exp(2)(n). We give an explicit formula for Exp(2)(n) and provide 2-factor expandable graphs of minimum size Exp(2)(n). (C) 2019 Elsevier B.V. All rights reserved.
Type
research article
Web of Science ID
WOS:000539095200007
Authors
Publication date
2020-08-15
Publisher
Published in
Volume
282
Start page
65
End page
79
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
June 25, 2020
Use this identifier to reference this record