Search

If $f:\mathbb{N}\rightarrow \mathbb{N}$ is a function, then let us say that $f$ is sublinear if \[\lim_{n\rightarrow +\infty}\frac{f(n)}{n}=0.\] If $G=(V,E)$ is a cubic graph and $c:E\rightarrow \{1,...,k\}$ is a proper $k$-edge-coloring of $G$, then an edge $e=uv$ of $G$ is poor (rich) in $c$, if the edges incident to $u$ and $v$ are colored with three (five) colors. An edge is abnormal if it is neither rich nor poor. The Petersen coloring conjecture of Jaeger states that any bridgeless cubic graph admits a proper 5-edge-coloring $c$, such that there is no an abnormal edge of $G$ with respect to $c$. For a proper 5-edge-coloring $c$ of $G$, let $N_G(c)$ be the set of abnormal edges of $G$ with respect to $c$. In this paper we show that (a) The Petersen coloring conjecture is equivalent to the statement that there is a sublinear function $f:\mathbb{N}\rightarrow \mathbb{N}$, such that all bridgeless cubic graphs admit a proper 5-edge-coloring $c$ with $|N_G(c)|\leq f(|V|)$; (b) for $k=2,3,4$, the statement that there is a sublinear function $f:\mathbb{N}\rightarrow \mathbb{N}$, such that all (cyclically) $k$-edge-connected cubic graphs admit a proper 5-edge-coloring $c$ with $|N_G(c)|\leq f(|V|)$ is equivalent to the statement that all (cyclically) $k$-edge-connected cubic graphs admit a proper 5-edge-coloring $c$ with $|N_G(c)|\leq 2k+1$., 10 pages, 4 figures

Let G be a finite graph (without loops and multiple edges) and let w : E ( G ) → [ 0 , + ∞ ) be a weight function on the edge set of G . We consider the ratio between the maximum weight of a perfect matching of G and the maximum weight of a matching of G . The parameter η ( G ) , introduced by Brazil & al. in Brazil et al. (2016), is defined as the minimum of such a ratio among all nonnegative edge weight assignments of G . In the present paper, we propose a way to compute a lower bound for the parameter η ( G ) , and we use it to prove that for every rational number q in the interval [ 0 , 1 ] there exists a graph G such that η ( G ) = q . Moreover, we further use the same method, in combination with some new arguments, to establish the value of η for Prism graphs and Mobius Ladders. Finally, we improve known results for Blanusa Snarks B 1 and B 2 by determining the exact value of η ( B 1 ) and η ( B 2 ) .

In 1994, it was conjectured by Fan and Raspaud that every simple bridgeless cubic graph has three perfect matchings whose intersection is empty. In this paper we answer a question recently proposed by Mkrtchyan and Vardanyan, by giving an equivalent formulation of the Fan-Raspaud Conjecture. We also study a possibly weaker conjecture originally proposed by the first author, which states that in every simple bridgeless cubic graph there exist two perfect matchings such that the complement of their union is a bipartite graph. Here, we show that this conjecture can be equivalently stated using a variant of Petersen-colourings, we prove it for graphs having oddness at most four and we give a natural extension to bridgeless cubic multigraphs and to certain cubic graphs having bridges., 17 pages, 11 figures

It is well known that the circular flow number of a bridgeless cubic graph can be computed in terms of certain partitions of its vertex set with prescribed properties. In the present paper, we first study some of these properties that turn out to be useful in order to make an efficient and practical implementation of an algorithm for the computation of the circular flow number of a bridgeless cubic graph. Using this procedure, we determine the circular flow number of all snarks on up to 36 vertices as well as the circular flow number of various famous snarks. After that, as combination of the use of this algorithm with new theoretical results, we present an infinite family of snarks of order 8 k + 2 whose circular flow numbers meet a general lower bound presented by Lukot’ka and Skoviera in 2008. In particular this answers a question proposed in their paper. Moreover, we improve the best known upper bound for the circular flow number of Goldberg snarks and we conjecture that this new upper bound is optimal.

A graph admitting a perfect matching has the Perfect-Matching-Hamiltonian property (for short the PMH-property) if each of its perfect matchings can be extended to a Hamiltonian cycle. In this paper we establish some sufficient conditions for a graph $G$ in order to guarantee that its line graph $L(G)$ has the PMH-property. In particular, we prove that this happens when $G$ is (i) a Hamiltonian graph with maximum degree at most $3$, (ii) a complete graph, or (iii) an arbitrarily traceable graph. Further related questions and open problems are proposed along the paper., Comment: 12 pages, 4 figures

A k -bisection of a bridgeless cubic graph G is a 2-colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes have order at most k . Ban and Linial conjectured that every bridgeless cubic graph admits a 2-bisection except for the Petersen graph. In this note, we prove Ban–Linial’s conjecture for claw-free cubic graphs.

A total coloring is equitable if the number of elements colored with each color differs by at most one, and the least integer for which a graph has such a coloring is called its equitable total chromatic number. Wang conjectured that the equitable total chromatic number of a multigraph of maximum degree is at most + 2 , and proved this for the case where 3 . Therefore, the equitable total chromatic number of a cubic graph is either 4 or 5, and in this work we prove that the problem of deciding whether it is 4 is NP-complete for bipartite cubic graphs.Furthermore, we present the first known Type1 cubic graphs with equitable total chromatic number5. All of them have, by construction, a small girth. We also find one infinite family of Type1 cubic graphs of girth5 having equitable total chromatic number 4. This motivates the following question: Does there exist Type1 cubic graphs of girth greater than5 and equitable total chromatic number5?

For some time the Petersen graph has been the only known Snark with circular flow number $5$ (or more, as long as the assertion of Tutte's $5$-flow Conjecture is in doubt). Although infinitely many such snarks were presented eight years ago by Macajova and Raspaud, the variety of known methods to construct them and the structure of the obtained graphs were still rather limited. We start this article with an analysis of sets of flow values, which can be transferred through flow networks with the flow on each edge restricted to the open interval $(1,4)$ modulo $5$. All these sets are symmetric unions of open integer intervals in the ring $\mathbb{R}/5\mathbb{Z}$. We use the results to design an arsenal of methods for constructing snarks $S$ with circular flow number $\phi_c(S)\ge 5$. As one indication to the diversity and density of the obtained family of graphs, we show that it is sufficiently rich so that the corresponding recognition problem is NP-complete., Comment: 30 pages - revised version

We show that "almost all" generalized Petersen graphs have total chromatic number 4. More precisely: for each integer k ? 2 , there exists an integer N ( k ) such that, for any n ? N ( k ) , the generalized Petersen graph G ( n , k ) has total chromatic number?4.

The problem of establishing the number of perfect matchings necessary to cover the edge-set of a cubic bridgeless graph is strictly related to a famous conjecture of Berge and Fulkerson. In this paper we prove that deciding whether this number is at most 4 for a given cubic bridgeless graph is NP-complete. We also construct an infinite family $\cal F$ of snarks (cyclically 4-edge-connected cubic graphs of girth at least five and chromatic index four) whose edge-set cannot be covered by 4 perfect matchings. Only two such graphs were known. It turns out that the family $\cal F$ also has interesting properties with respect to the shortest cycle cover problem. The shortest cycle cover of any cubic bridgeless graph with $m$ edges has length at least $\tfrac43m$, and we show that this inequality is strict for graphs of $\cal F$. We also construct the first known snark with no cycle cover of length less than $\tfrac43m+2$., Comment: 17 pages, 8 figures

A conjecture of Berge and Fulkerson (1971) states that every cubic bridgeless graph contains 6 perfect matchings covering each edge precisely twice, which easily implies that every cubic bridgeless graph has three perfect matchings with empty intersection (this weaker statement was conjectured by Fan and Raspaud in 1994). Let $m_t$ be the supremum of all reals $\alpha\le 1$ such that for every cubic bridgeless graph $G$, there exist $t$ perfect matchings of $G$ covering a fraction of at least $\alpha$ of the edges of $G$. It is known that the Berge-Fulkerson conjecture is equivalent to the statement that $m_5=1$, and implies that $m_4=\tfrac{14}{15}$ and $m_3=\tfrac45$. In the first part of this paper, we show that $m_4=\tfrac{14}{15}$ implies $m_3=\tfrac45$, and $m_3=\tfrac45$ implies the Fan-Raspaud conjecture, strengthening a recent result of Tang, Zhang, and Zhu. In the second part of the paper, we prove that for any $2\le t \le 4$ and for any real $\tau$ lying in some appropriate interval, deciding whether a fraction of more than (resp. at least) $\tau$ of the edges of a given cubic bridgeless graph can be covered by $t$ perfect matching is an NP-complete problem. This resolves a conjecture of Tang, Zhang, and Zhu., Comment: 13 pages, 5 figures - revised version

Fullerene graphs are trivalent plane graphs with only hexagonal and pentagonal faces. They are often used to model large carbon molecules: each vertex represents a carbon atom and the edges represent chemical bonds. A totally symmetric Kekule structure in a fullerene graph is a set of independent edges which is fixed by all symmetries of the fullerene and molecules with totally symmetric Kekule structures could have special physical and chemical properties, as suggested in [Austin, S.J, and J. Baker, P. W. Fowler, D. E. Manolopoulos, Bond-stretch Isomerism and the Fullerenes, J. Chem. Soc. Perkin Trans. 2 (1994), 2319–2323] and [Rogers, K.M., and P. W. Fowler, Leapfrog fullerenes, Huckel bond order and Kekule structures, J. Chem. Soc. Perkin Trans. 2 (2001), 18–22]. All fullerenes with at least ten symmetries were studied in [Graver, J.E. The Structure of Fullerene Signature, DIMACS Series of Discrete Mathematics and Theoretical Computer Science 64, AMS (2005), 137–166.] and a complete catalog was given in [Graver, J. E. Catalog of All Fullerene with Ten or More Symmetries DIMACS Series of Discrete Mathematics and Theoretical Computer Science 64 AMS (2005), 167–188]. Starting from this catalog in [Bogaerts, M., and G. Mazzuoccolo, G.Rinaldi, Totally symmetric Kekule structures in fullerene graphs with ten or more symmetries, MATCH Communications in Mathematical and in Computer Chemistry 69 (2013), 677–705] we established exactly which of them have at least one totally symmetric Kekule structure.

An automorphism group G of a 1-factorization of the complete multipartite graph K m×n consists of permutations of the vertices of the graph mapping factors to factors. In this paper, we give a complete answer to the existence problem of a 1-factorization of K m×n admitting a cyclic or dihedral group acting sharply transitively on the vertices of the graph., info:eu-repo/semantics/published

The automorphic G-chromatic index of a graph Γ is the minimum integer m for which Γ has a proper edge-coloring with m colors which is preserved by the full automorphism group G of Γ. We determine the automorphic G-chromatic index of each member of four infinite classes of snarks: type I Blanusa snarks, type II Blanusa snarks, Flower snarks and Goldberg snarks.

In this paper we define the automorphic H-chromatic index of a graph Γ as the minimum integer m for which Γ has a proper edge-coloring with m colors which is preserved by a given automorphism group H of Γ. After the description of some properties, we determine upper bounds for this index when H is a cyclic group of prime order. We also show that these upper bounds are best possible in a number of instances.

We consider 2-factorizations of complete graphs that possess an automorphism group fixing k⩾0 vertices and acting sharply transitively on the others. We study the structures of such factorizations and consider the cases in which the group is either abelian or dihedral in some more details. Combining results of the first part of the paper with a result of D. Bryant, J Combin Des, 12 (2004), 147–155, we prove that the class of 2-factorizations of complete graphs is universal. Namely each finite group is the full automorphism group of a 2-factorization of the class. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 211-228, 2009

Let be a 2-factorization of the complete graph Kv admitting an automorphism group G acting doubly transitively on the set of vertices. The vertex-set V(Kv) can then be identified with the point-set of AG(n, p) and each 2-factor of is the union of p-cycles which are obtained from a parallel class of lines of AG(n, p) in a suitable manner, the group G being a subgroup of A G L(n, p) in this case. The proof relies on the classification of 2-(v, k, 1) designs admitting a doubly transitive automorphism group. The same conclusion holds even if G is only assumed to act doubly homogeneously. © 2006 Wiley Periodicals, Inc. J Combin Designs

We consider one–factorizations of complete graphs which possess an automorphism group fixing k ≥ 0 vertices and acting regularly (i.e., sharply transitively) on the others. Since the cases k = 0 and k = 1 are well known in literature, we study the case k≥ 2 in some detail. We prove that both k and the order of the group are even and the group necessarily contains k − 1 involutions. Constructions for some classes of groups are given. In particular we extend the result of [7]: let G be an abelian group of even order and with k − 1 involutions, a one–factorization of a complete graph admitting G as an automorphism group fixing k vertices and acting regularly on the others can be constructed.