Logo del repository
  1. Home
 
Opzioni

An ILP Approach to Determine Smallest 4-Regular Nonhamiltonian, Nontraceable, and Nonhomogeneously Taceable Graphs

Lancia Giuseppe
•
Pippia Eleonora
•
Rinaldi Franca
2022
  • journal article

Periodico
JOURNAL OF APPLIED AND INDUSTRIAL MATHEMATICS
Abstract
Abstract: In this paper we study some open questions related to the smallest order (Formula presented.)-regular graph which has a connectivity property(Formula presented.) but does not have a hamiltonian property (Formula presented.). In particular, (Formula presented.) is either connectivity, (Formula presented.)-toughness and (Formula presented.) is hamiltonicity, homogeneous traceability or traceability. A standardtheoretical approach to these questions had already been used in the literature, but in many casesdid not succeed in determining the exact value of (Formula presented.). Here we have chosen to use Integer Linear Programming and to encode thegraphs that we are looking for as the binary solutions to a suitable set of linear inequalities. Thisway, there would exist a graph of order n with certain properties if and only if the corresponding ILP had a feasiblesolution, which we have determined through a branch-and-cut procedure. By using our approach,we have been able to compute (Formula presented.) for all the pairs of considered properties with the exception of (Formula presented.) traceability. Even in this last case, we have nonetheless significantly reducedthe interval (Formula presented.) in which (Formula presented.) was known to lie. Finally, we have shown that for each (Formula presented.) ((Formula presented.) in the last case) there exists a (Formula presented.)-regular graph on (Formula presented.) vertices which has property (Formula presented.) but not property (Formula presented.).
DOI
10.1134/S1990478922020077
Archivio
https://hdl.handle.net/11390/1233706
info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-85142203291
https://ricerca.unityfvg.it/handle/11390/1233706
Diritti
closed access
Soggetti
  • 1-tough graph

  • 4-regular graph

  • branch-and-cut

  • Hamiltonian graph

  • homogeneously traceab...

  • Integer Linear Progra...

  • traceable graph

google-scholar
Get Involved!
  • Source Code
  • Documentation
  • Slack Channel
Make it your own

DSpace-CRIS can be extensively configured to meet your needs. Decide which information need to be collected and available with fine-grained security. Start updating the theme to match your nstitution's web identity.

Need professional help?

The original creators of DSpace-CRIS at 4Science can take your project to the next level, get in touch!

Realizzato con Software DSpace-CRIS - Estensione mantenuta e ottimizzata da 4Science

  • Impostazioni dei cookie
  • Informativa sulla privacy
  • Accordo con l'utente finale
  • Invia il tuo Feedback