Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Minimal graphs for 2-factor extension
 
research article

Minimal graphs for 2-factor extension

Costa, M-C
•
de Werra, D.  
•
Picouleau, C.
August 15, 2020
Discrete Applied Mathematics

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.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.dam.2019.11.022
Web of Science ID

WOS:000539095200007

Author(s)
Costa, M-C
de Werra, D.  
Picouleau, C.
Date Issued

2020-08-15

Publisher

ELSEVIER

Published in
Discrete Applied Mathematics
Volume

282

Start page

65

End page

79

Subjects

Mathematics, Applied

•

Mathematics

•

2-factor

•

minimum expandable graph

•

reliability

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ROSE  
Available on Infoscience
June 25, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/169603
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés