A Faster Test for 4-Flow-Criticality in Snarks

André Breda Carneiro; Cândida Nunes da Silva; Brendan McKay

doi:10.1016/j.endm.2015.07.033

A Faster Test for 4-Flow-Criticality in Snarks

André Breda Carneiro
, Cândida Nunes da Silva
, Brendan McKay

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

No snark has a 4-flow. A snark G is 4-edge-critical (or 4-vertex-critical) if, for every edge e (or pair of vertices (u, v)) of G, the graph obtained after contracting e (or identifying u and v) has a 4-flow. It is known that to determine whether a graph has a 4-flow is an NP-complete problem. In this paper, we present an improved exponential time algorithm to check whether a snark is 4-edge-critical (or 4-vertex-critical) or not. The use of our algorithm allowed us to determine the number of 4-edge-critical and 4-vertex-critical snarks of order at most 36.

Original language	English
Pages (from-to)	193-198
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	50
DOIs	https://doi.org/10.1016/j.endm.2015.07.033
Publication status	Published - 1 Dec 2015

Access to Document

10.1016/j.endm.2015.07.033

Cite this

@article{81ecf1548af746f4a9a9230530a99099,

title = "A Faster Test for 4-Flow-Criticality in Snarks",

abstract = "No snark has a 4-flow. A snark G is 4-edge-critical (or 4-vertex-critical) if, for every edge e (or pair of vertices (u, v)) of G, the graph obtained after contracting e (or identifying u and v) has a 4-flow. It is known that to determine whether a graph has a 4-flow is an NP-complete problem. In this paper, we present an improved exponential time algorithm to check whether a snark is 4-edge-critical (or 4-vertex-critical) or not. The use of our algorithm allowed us to determine the number of 4-edge-critical and 4-vertex-critical snarks of order at most 36.",

keywords = "Nowhere-zero k-flows, Snarks, Tutte's Flow Conjectures",

author = "Carneiro, \{Andr{\'e} Breda\} and \{da Silva\}, \{C{\^a}ndida Nunes\} and Brendan McKay",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2015",

month = dec,

day = "1",

doi = "10.1016/j.endm.2015.07.033",

language = "English",

volume = "50",

pages = "193--198",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - A Faster Test for 4-Flow-Criticality in Snarks

AU - Carneiro, André Breda

AU - da Silva, Cândida Nunes

AU - McKay, Brendan

PY - 2015/12/1

Y1 - 2015/12/1

N2 - No snark has a 4-flow. A snark G is 4-edge-critical (or 4-vertex-critical) if, for every edge e (or pair of vertices (u, v)) of G, the graph obtained after contracting e (or identifying u and v) has a 4-flow. It is known that to determine whether a graph has a 4-flow is an NP-complete problem. In this paper, we present an improved exponential time algorithm to check whether a snark is 4-edge-critical (or 4-vertex-critical) or not. The use of our algorithm allowed us to determine the number of 4-edge-critical and 4-vertex-critical snarks of order at most 36.

AB - No snark has a 4-flow. A snark G is 4-edge-critical (or 4-vertex-critical) if, for every edge e (or pair of vertices (u, v)) of G, the graph obtained after contracting e (or identifying u and v) has a 4-flow. It is known that to determine whether a graph has a 4-flow is an NP-complete problem. In this paper, we present an improved exponential time algorithm to check whether a snark is 4-edge-critical (or 4-vertex-critical) or not. The use of our algorithm allowed us to determine the number of 4-edge-critical and 4-vertex-critical snarks of order at most 36.

KW - Nowhere-zero k-flows

KW - Snarks

KW - Tutte's Flow Conjectures

UR - https://www.scopus.com/pages/publications/84953390348

U2 - 10.1016/j.endm.2015.07.033

DO - 10.1016/j.endm.2015.07.033

M3 - Article

SN - 1571-0653

VL - 50

SP - 193

EP - 198

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

A Faster Test for 4-Flow-Criticality in Snarks

Abstract

Access to Document

Other files and links

Fingerprint

Cite this