Flow resistance to resistance ratios in cubic graphs

被引：0

作者：

Allie, Imran ^{[1
]}

Macajova, Edita ^{[2
]}

Skoviera, Martin ^{[2
]}

机构：

[1] Univ Cape Town, Dept Math & Appl Math, ZA-7700 Cape Town, South Africa

[2] Comenius Univ, Dept Comp Sci, Bratislava 84248, Slovakia

来源：

DISCRETE APPLIED MATHEMATICS | 2024年 / 342卷

关键词：

Flow resistance; Resistance; Snarks; Cubic graphs;

D O I：

10.1016/j.dam.2023.09.026

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The resistance of a cubic graph is the smallest number of edges whose removal produces a 3-edge-colourable graph. The flow resistance is the minimum number of zeros in an integer 4-flow on the graph. Fiol et al. (2018) made a conjecture that the flow resistance of a bridgeless cubic graph never exceeds its resistance. The conjecture has recently been proved to be false by displaying a family of nontrivial snarks with resistance n and flow resistance 2n (Allie et al., 2022). In this paper, we strengthen the result by showing that the ratio of the flow resistance to the resistance of a snark can be arbitrarily large.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

引用

页码：362 / 367

页数：6

共 6 条

[1] 3-Critical Subgraphs of Snarks [J].

Allie, Imran .

ANNALS OF COMBINATORICS, 2022, 26 (02) :501-510

[2] Snarks with resistance n and flow resistance 2n [J].

Allie, Imran ;

Macajova, Edita ;

Skoviera, Martin .

ELECTRONIC JOURNAL OF COMBINATORICS, 2022, 29 (01)

[3]

Fiol MA, 2018, ELECTRON J COMB, V25

[4] Snarks without small cycles [J].

Kochol, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1996, 67 (01) :34-47

[5] CRITICAL AND FLOW-CRITICAL SNARKS COINCIDE [J].

Macajova, Edita ;

Skoviera, Martin .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2021, 41 (02) :503-511

[6] Classifications and characterizations of snarks [J].

Steffen, E .

DISCRETE MATHEMATICS, 1998, 188 (1-3) :183-203

← 1 →