Search

The perfect matching index of a cubic graph G, denoted by \pi (G), is the smallest number of perfect matchings that cover all the edges of G. According to the Berge--Fulkerson conjecture, \pi (G) \leq 5 for every bridgeless cubic graph G. The class of graphs with \pi \geq 5 is of particular interest as many conjectures and open problems, including the famous cycle double cover conjecture, can be reduced to it. Although nontrivial examples of such graphs are very difficult to find, a few infinite families are known, all with circular flow number \Phi c(G) = 5. It has been therefore suggested [Abreu et al., Electron. J. Combin., 23 (2016), P3.54] that \pi (G) \geq 5 might imply \Phi c(G) \geq 5. In this article we dispel these hopes and present a family of cyclically 4-edgeconnected cubic graphs of girth at least 5 with \pi \geq 5 and \Phi c \leq 4 + 2 3. [ABSTRACT FROM AUTHOR]

A graph G is called (r, s)-edge-choosable if for every assignment of sets of size r to the edges of G it is possible to choose for every edge an s-element subset from its set such that the subsets chosen for any pair of adjacent edges are disjoint. The list fractional chromatic index of a graph G is the infimum of all numbers r/s for which G is (r, s)-edge-choosable. Mohar [http://www.fmf.uni-lj.si/~mohar/(June 2003)] posed a problem asking whether every cubic graph is (7,2)-edge-choosable. In 2009, Cranston and West [SIAM J. Discrete Math., 23 (2009), pp. 872-881] showed that every 3-edge-colorable cubic graph is (7,2)-edge-choosable and gave a sufficient condition with the help of which they proved that many non-3-edge-colorable-cubic graphs are (7,2)-edge-choosable. In this paper we prove that every bridgeless cubic graph is (7,2)-edge-choosable. We show that this result cannot be improved in the family of all cubic graphs, in the sense that there exists a cubic graph with list fractional chromatic index 7/2. The original question of Mohar remains open, and we further pose several related problems. [ABSTRACT FROM AUTHOR]

Let G be an undirected graph with a set of vertices V and a set of edges E. Given an integer r, we assign at most r labels (representing "resources") to each vertex. We say that such an assignment is an r-configuration if, for each label c, the vertices labeled by c form a dominating set for G. In this paper, we are interested in the maximum number, Dr(G), of labels that can be assigned to the vertices of graph G by an r-configuration. The decision problem "D1(G) ≥ K?" (known as the domatic number problem) is NP-complete. We first investigate Dr(G) for general graphs and establish bounds on Dr(G) in terms of D1(G) and the minimum vertex degree of G. We then discuss Dr(G) for d-regular graphs. We clearly have Dr(G) ≤ r(d + 1). We show that the problem of testing if Dr(G) = r(d + 1) is solvable in polynomial time for d-regular graphs with ∣V∣ = 2(d + 1), but is NP-complete for those with ∣V∣ = a(d + 1) for some integer a ≥ 3. Finally, we discuss cubic (i.e., 3-regular) graphs. It is easy to show 2r ≤ Dr(G) ≤ 4r for cubic graphs. We show that the decision problem for D1(G) = K is co-NP-complete for K = 2 and is NP-complete for K = 4. Although there are many cubic graphs G with D1(G) = 2, surprisingly, every cubic graph has a 2-configuration with five labels, i.e., D2(G) ≥ 5 and such a 2-configuration can be constructed in polynomial time. We use this fact to show Dr(G) ≥. ⌊5r/2⌋ in general. [ABSTRACT FROM AUTHOR]

It is known that a 3-edge-connected graph has a spanning even subgraph in which every component contains at least five vertices, and the lower bound is best possible. A natural question arises of whether we can improve the lower bound by changing the spanning property with the dominating property. In this paper, we show that a 3-edge-connected cubic graph has a dominating even subgraph in which every component contains at least six vertices. [ABSTRACT FROM AUTHOR]

The well-known shortest cycle cover conjecture suggests that every bridgeless graph G can have its edges covered with a collection of cycles of total length not exceeding 7 5 · |E(G)|. This conjecture is particularly interesting for cubic graphs, where the largest values of the ratio between the length of a shortest cycle cover and the number of edges are known. The covering ratio 7/5 is the best possible, being reached by the Petersen graph whose shortest cycle cover has length 21. There exist infinitely many cubic graphs with cyclic connectivity 2, as well as those with cyclic connectivity 3, whose covering ratio equals 7/5. By contrast, all cyclically 4-edge-connected cubic graphs where the length of a shortest cycle cover is known have covering ratio close to the natural lower bound which equals 4/3. In line with this observation, Brinkmannn et al. [J. Combin. Theory Ser. B, 103 (2013), pp. 468-488] made a conjecture that every cyclically 4-edge-connected cubic graph has a cycle cover of length at most 4 3m + o(m), where m is the number of edges. We disprove this conjecture by exhibiting an infinite family of cyclically 4-edge-connected cubic graphs Gk, k = 2, such that the length of a shortest cycle cover of each Gk is at least (4 3 + 1 69)|E(Gk)|. [ABSTRACT FROM AUTHOR]

Carvalho, Lucchesi, and Murty [J. Combin. Theory Ser. B, 92 (2004), pp. 319--324, Theorem 3.5] presented a proof of a theorem of Reed and Wakabayashi that a brick G is nonsolid if and only if there exist two vertex-disjoint odd cycles C1 and C2 such that G V (C1 ∪ C2) has a perfect matching. Consequently, every brick with no two vertex-disjoint odd cycles is solid. Recently, Lucchesi et al. [SIAM J. Discrete Math., 32 (2018), pp. 1478--1501] constructed infinite families of solid bricks containing two vertex-disjoint odd cycles. Noticing that none of these graphs is cubic, they conjectured that no cubic solid brick contains two vertex-disjoint odd cycles. In this note, we present an infinite family of graphs showing that this conjecture fails. We further show that the minimum counterexample is unique, which has 12 vertices. [ABSTRACT FROM AUTHOR]

We show that every bridgeless cubic graph G with m edges has a cycle cover of length at most 1.6m. Moreover, if G does not contain any intersecting circuits of length 5, then G has a cycle cover of length 212/135 ·m ≈ 1.570m, and if G contains no 5-circuits, then it has a cycle cover of length at most 14/9·m ≈ 1.556m. To prove our results, we show that each 2-edge-connected cubic graph G on n vertices has a 2-factor containing at most n/10+f(G) circuits of length 5, where the value of f(G) depends only on the presence of several subgraphs arising from the Petersen graph. As a corollary we get that each 3-edge-connected cubic graph on n vertices has a 2-factor containing at most n/9 circuits of length 5, and each 4-edge-connected cubic graph on n vertices has a 2-factor containing at most n/10 circuits of length 5. [ABSTRACT FROM AUTHOR]

For every rational number r such that 3 < r < 3 + 1/3, we construct an infinite family of cubic graphs with circular chromatic index r. Our construction disproves a conjecture of Zhu that there is no bounded increasing infinite sequence in the set of circular chromatic indices of graphs [Topics in Discrete Mathematics, Dedicated to Jarik Nešetřil on the Occasion of his 60th Birthday, Algorithms Combin. 26, M. Klazar, J. Kratochvíl, M. Loebl, J. Matoušek, R. Thomas, and P. Valtr, eds., Springer, Berlin, 2006, pp. 497-550]. We also describe a sequence of graphs whose circular chromatic indices converge to 3 + 1/3 from above. [ABSTRACT FROM AUTHOR]

We prove that every n-vertex cubic bridgeless graph has at least n/2 perfect matchings and give a list of all 17 such graphs thathave less than n/2 + 2 perfect matchings. [ABSTRACT FROM AUTHOR]