Colourings of cubic graphs inducing isomorphic monochromatic subgraphs

A -bisection of a bridgeless cubic graph is a -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 ( monochromatic components in what follows) have order at most . Ban and Linial Conjectured that every bridgeless cubic graph admits a -bisection except for the Petersen graph. A similar problem for the edge set of cubic graphs has been studied: Wormald conjectured that every cubic graph with has a -edge colouring such that the two monochromatic subgraphs are isomorphic linear forests (ie, a forest whose components are paths). Finally, Ando conjectured that every cubic graph admits a bisection such that the two induced monochromatic subgraphs are isomorphic. In this paper, we provide evidence of a strong relation of the conjectures of Ban-Linial and Wormald with Ando's Conjecture. Furthermore, we also give computational and theoretical evidence in their support. As a result, we pose some open problems stronger than the above-mentioned conjectures. Moreover, we prove Ban-Linial's Conjecture for cubic-cycle permutation graphs. As a by-product of studying -edge colourings of cubic graphs having linear forests as monochromatic components, we also give a negative answer to a problem posed by Jackson and Wormald about certain decompositions of cubic graphs into linear forests.     

Grünbaum colorings of even triangulations on surfaces

A Grünbaum coloring of a triangulation G is a map c : such that for each face f of G, the three edges of the boundary walk of f are colored by three distinct colors. By Four Color Theorem, it is known that every triangulation on the sphere has a Grünbaum coloring. So, in this article, we investigate the question whether each even (i.e., Eulerian) triangulation on a surface with representativity at least r has a Grünbaum coloring. We prove that, regardless of the representativity, every even triangulation on a surface has a Grünbaum coloring as long as is the projective plane, the torus, or the Klein bottle, and we observe that the same holds for any surface with sufficiently large representativity. On the other hand, we construct even triangulations with no Grünbaum coloring and representativity , and 3 for all but finitely many surfaces. In dual terms, our results imply that no snark admits an even map on the projective plane, the torus, or the Klein bottle, and that all but finitely many surfaces admit an even map of a snark with representativity at least 3.     

Generation of Cubic Graphs and Snarks with Large Girth

We describe two new algorithms for the generation of all non‐isomorphic cubic graphs with girth at least that are very efficient for and show how these algorithms can be restricted to generate snarks with girth at least k. Our implementation of these algorithms is more than 30, respectively 40 times faster than the previously fastest generator for cubic graphs with girth at least six and seven, respectively. Using these generators we have also generated all nonisomorphic snarks with girth at least six up to 38 vertices and show that there are no snarks with girth at least seven up to 42 vertices. We present and analyze the new list of snarks with girth 6.     

A counterexample to the odd 2–factored snarks conjecture

A snark is a cubic cyclically 4–edge connected graph with edge chromatic number four and girth at least five. We say that a graph G is odd 2–factored if for each 2–factor F of G each cycle of F is odd. In this extended abstract, we present a method for constructing odd 2–factored snarks. In particular, we construct two families of odd 2–factored snarks of order 26 and 34 that disprove a previous conjecture by some of the authors.     

Snarks with given real flow numbers

We show that for each rational number r such that 4<r?5 there exist infinitely many cyclically 4‐edge‐connected cubic graphs of chromatic index 4 and girth at least 5—that is, snarks—whose flow number equals r. This answers a question posed by Pan and Zhu [Construction of graphs with given circular flow numbers, J Graph Theory 43 [2003], 304–318]. © 2011 Wiley Periodicals, Inc. J Graph Theory 68: 189‐201, 2011     

ON CLASSES OF REGULAR GRAPHS WITH CONSTANT METRIC DIMENSION

In this paper,we are dealing with the study of the metric dimension of some classes of regular graphs by considering a class of bridgeless cubic graphs called the flower snarks Jn,a class of cubic convex polytopes considering the open problem raised in [M.Imran et al.,families of plane graphs with constant metric dimension,Utilitas Math.,in press] and finally Harary graphs H 5,n by partially answering to an open problem proposed in [I.Javaid et al.,Families of regular graphs with constant metric dimension,Utilitas Math.,2012,88:43-57].We prove that these classes of regular graphs have constant metric dimension.     

Real flow number and the cycle rank of a graph

This article establishes a relationship between the real (circular) flow number of a graph and its cycle rank. We show that a connected graph with real flow number p/q + 1, where p and q are two relatively prime numbers must have cycle rank at least p + q ? 1. A special case of this result yields that the real flow number of a 2‐connected cubic graph with chromatic index 4 and order at most 8k + 4 is bounded from below by 4 + 1/k. Using this bound we prove that the real flow number of the Isaacs snark I_{2k + 1} equals 4 + 1/k, completing the upper bound due to Steffen [Steffen, J Graph Theory 36 (2001), 24–34]. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 11–16, 2008     

A survey on snarks and new results: Products,reducibility and a computer search

In this paper we survey recent results and problems of both theoretical and algorithmic character on the construction of snarks—non-trivial cubic graphs of class two, of cyclic edge-connectivity at least 4 and with girth ≥ 5. We next study the process, also considered by Cameron, Chetwynd, Watkins, Isaacs, Nedela, and Sˇkoviera, of splitting a snark into smaller snarks which compose it. This motivates an attempt to classify snarks by recognizing irreducible and prime snarks and proving that all snarks can be constructed from them. As a consequence of these splitting operations, it follows that any snark (other than the Petersen graph) of order ≤ 26 can be built as either a dot product or a square product of two smaller snarks. Using a new computer algorithm we have confirmed the computations of Brinkmann and Steffen on the classification of all snarks of order less than 30. Our results recover the well-known classification of snarks of order not exceeding 22. Finally, we prove that any snark G of order ≤ 26 is almost Hamiltonian, in the sense that G has at least one vertex v for which G \ v is Hamiltonian. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 57–86, 1998     

Cubic Graphs with Large Circumference Deficit

The circumference of a graph G is the length of a longest cycle. By exploiting our recent results on resistance of snarks, we construct infinite classes of cyclically 4‐, 5‐, and 6‐edge‐connected cubic graphs with circumference ratio bounded from above by 0.876, 0.960, and 0.990, respectively. In contrast, the dominating cycle conjecture implies that the circumference ratio of a cyclically 4‐edge‐connected cubic graph is at least 0.75. Up to our knowledge, no upper bounds on this ratio have been known before for cubic graphs with cyclic edge‐connectivity above 3. In addition, we construct snarks with large girth and large circumference deficit, solving Problem 1 proposed in [J. Hägglund and K. Markström, On stable cycles and cycle double covers of graphs with large circumference, Disc Math 312 (2012), 2540–2544].     

Thomassen's conjecture implies polynomiality of 1‐Hamilton‐connectedness in line graphs

A graph G is 1‐Hamilton‐connected if G?x is Hamilton‐connected for every x∈V(G), and G is 2‐edge‐Hamilton‐connected if the graph G+ X has a hamiltonian cycle containing all edges of X for any X?E⁺(G) = {xy| x, y∈V(G)} with 1≤|X|≤2. We prove that Thomassen's conjecture (every 4‐connected line graph is hamiltonian, or, equivalently, every snark has a dominating cycle) is equivalent to the statements that every 4‐connected line graph is 1‐Hamilton‐connected and/or 2‐edge‐Hamilton‐connected. As a corollary, we obtain that Thomassen's conjecture implies polynomiality of both 1‐Hamilton‐connectedness and 2‐edge‐Hamilton‐connectedness in line graphs. Consequently, proving that 1‐Hamilton‐connectedness is NP‐complete in line graphs would disprove Thomassen's conjecture, unless P = NP. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 241–250, 2012