Academic Bibliography

 Search 200 years of publications by Ghent University researchers.
Advanced search
1 file | 385.31 KB
Add to list
  1. Search results
  2. On the Frank number and nowhere-zero ...

On the Frank number and nowhere-zero flows on graphs

Jan Goedgebeur (UGent) , Edita Macajova and Jarne Renders
(2023) GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2023. In Lecture Notes in Computer Science 14093. p.363-375
Author
Organization
Abstract
An edge e of a graph G is called deletable for some orientation o if the restriction of o to G - e is a strong orientation. In 2021, Horsch and Szigeti proposed a new parameter for 3-edge-connected graphs, called the Frank number, which refines k-edge-connectivity. The Frank number is defined as the minimum number of orientations of G for which every edge of G is deletable in at least one of them. They showed that every 3-edge-connected graph has Frank number at most 7 and that in case these graphs are also 3-edge-colourable graphs the parameter is at most 3. Here we strengthen the latter result by showing that such graphs have Frank number 2, which also confirms a conjecture by Bar ' at and Bl ' azsik. Furthermore, we prove two sufficient conditions for cubic graphs to have Frank number 2 and use them in an algorithm to computationally show that the Petersen graph is the only cyclically 4-edge-connected cubic graph up to 36 vertices having Frank number greater than 2.
Keywords
Frank number, Connectivity, Orientation, Snark, Nowhere-zero flows

Downloads

  • Download
    (...).pdf
    • full text (Published version)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 385.31 KB

Citation

Please use this url to cite or link to this publication:

MLA
Goedgebeur, Jan, et al. “On the Frank Number and Nowhere-Zero Flows on Graphs.” GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2023, vol. 14093, Springer, 2023, pp. 363–75, doi:10.1007/978-3-031-43380-1_26.
APA
Goedgebeur, J., Macajova, E., & Renders, J. (2023). On the Frank number and nowhere-zero flows on graphs. GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2023, 14093, 363–375. https://doi.org/10.1007/978-3-031-43380-1_26
Chicago author-date
Goedgebeur, Jan, Edita Macajova, and Jarne Renders. 2023. “On the Frank Number and Nowhere-Zero Flows on Graphs.” In GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2023, 14093:363–75. Cham: Springer. https://doi.org/10.1007/978-3-031-43380-1_26.
Chicago author-date (all authors)
Goedgebeur, Jan, Edita Macajova, and Jarne Renders. 2023. “On the Frank Number and Nowhere-Zero Flows on Graphs.” In GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2023, 14093:363–375. Cham: Springer. doi:10.1007/978-3-031-43380-1_26.
Vancouver
1.
Goedgebeur J, Macajova E, Renders J. On the Frank number and nowhere-zero flows on graphs. In: GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2023. Cham: Springer; 2023. p. 363–75.
IEEE
[1]
J. Goedgebeur, E. Macajova, and J. Renders, “On the Frank number and nowhere-zero flows on graphs,” in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2023, Fribourg, SWITZERLAND, 2023, vol. 14093, pp. 363–375.
@inproceedings{01HS8PWYK8PFRFEGXXC2MJJJ1V,
  abstract     = {{An edge e of a graph G is called deletable for some orientation o if the restriction of o to G - e is a strong orientation. In 2021, Horsch and Szigeti proposed a new parameter for 3-edge-connected graphs, called the Frank number, which refines k-edge-connectivity. The Frank number is defined as the minimum number of orientations of G for which every edge of G is deletable in at least one of them. They showed that every 3-edge-connected graph has Frank number at most 7 and that in case these graphs are also 3-edge-colourable graphs the parameter is at most 3. Here we strengthen the latter result by showing that such graphs have Frank number 2, which also confirms a conjecture by Bar ' at and Bl ' azsik. Furthermore, we prove two sufficient conditions for cubic graphs to have Frank number 2 and use them in an algorithm to computationally show that the Petersen graph is the only cyclically 4-edge-connected cubic graph up to 36 vertices having Frank number greater than 2.}},
  author       = {{Goedgebeur, Jan and  Macajova, Edita and  Renders, Jarne}},
  booktitle    = {{GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2023}},
  isbn         = {{9783031433795}},
  issn         = {{0302-9743}},
  keywords     = {{Frank number,Connectivity,Orientation,Snark,Nowhere-zero flows}},
  language     = {{eng}},
  location     = {{Fribourg, SWITZERLAND}},
  pages        = {{363--375}},
  publisher    = {{Springer}},
  title        = {{On the Frank number and nowhere-zero flows on graphs}},
  url          = {{http://doi.org/10.1007/978-3-031-43380-1_26}},
  volume       = {{14093}},
  year         = {{2023}},
}
Altmetric
View in Altmetric
Web of Science
Times cited: