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
Author(s)
Date Issued
2020-08-15
Publisher
Published in
Volume
282
Start page
65
End page
79
Editorial or Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Available on Infoscience
June 25, 2020
Use this identifier to reference this record