A conjecture of Mácajová and Skoviera asserts that every bridgeless cubic graph has two perfect matchings whose intersection does not contain any odd edge cut. We prove this conjecture for graphs with few vertices and we give a stronger result for traceable graphs.
A normal partition of the edges of a cubic graph is a partition into trails (no repeated edge) such that each vertex is the end vertex of exactly one trail of the partition. We investigate this notion and give some results and problems.
If G is a bridgeless cubic graph, Fulkerson conjectured that we can find 6 perfect matchings (a Fulkerson covering) with the property that every edge of G is contained in exactly two of them. A consequence of the Fulkerson conjecture would be that every bridgeless cubic graph has 3 perfect matchings with empty intersection (this problem is known as the Fan Raspaud Conjecture). A FR-triple is a set of 3 such perfect matchings. We show here how to derive a Fulkerson covering from two FR-triples. Moreover,...
We consider cubic graphs formed with k ≥ 2 disjoint claws (0 ≤ i ≤ k-1) such that for every integer i modulo k the three vertices of degree 1 of are joined to the three vertices of degree 1 of and joined to the three vertices of degree 1 of . Denote by the vertex of degree 3 of and by T the set . In such a way we construct three distinct graphs, namely FS(1,k), FS(2,k) and FS(3,k). The graph FS(j,k) (j ∈ 1,2,3) is the graph where the set of vertices induce j cycles (note that the graphs...
A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. In this paper we consider linear partitions of cubic simple graphs for which it is well known that la(G) = 2. A linear partition is said to be odd whenever each path of has odd length and semi-odd whenever each path of (or each path of ) has odd length. In [2] Aldred...
Page 1