MAX CUT in cubic graphs

We present an improved semidefinite programming based approximation algorithm for the MAX CUT problem in graphs of maximum degree at most 3. The approximation ratio of the new algorithm is at least 0.9326. This improves, and also somewhat simplifies, a result of Feige, Karpinski and Langberg. We also observe that results of Hopkins and Staton and of Bondy and Locke yield a simple combinatorial 4/5-approximation algorithm for the problem. Finally, we present a combinatorial 22/27-approximation algorithm for the MAX CUT problem for regular cubic graphs.     

Path factors in cubic graphs

Let ? be a set of connected graphs. An ?‐factor of a graph is its spanning subgraph such that each component is isomorphic to one of the members in ?. Let P_k denote the path of order k. Akiyama and Kano have conjectured that every 3‐connected cubic graph of order divisible by 3 has a {P₃}‐factor. Recently, Kaneko gave a necessary and sufficient condition for a graph to have a {P₃, P₄, P₅}‐factor. As a corollary, he proved that every cubic graph has a {P₃, P₄, P₅}‐factor. In this paper, we prove that every 2‐connected cubic graph of order at least six has a {P_k ∣ k ≥ , 6}‐factor, and hence has a {P₃, P₄}‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 188–193, 2002; DOI 10.1002/jgt.10022     

Bounded-excess flows in cubic graphs

An (r, α)-bounded-excess flow ((r, α)-flow) in an orientation of a graph G = (V, E) is an assignment f : E → [1, r−1], such that for every vertex x ∈ V, $|{\sum }_{e\in E^{+}\left(x\right)}f\left(e\right)-{\sum }_{e\in E^{-}\left(x\right)}f\left(e\right)|\le \alpha$. E⁺(x), respectively E⁻(x), is the set of edges directed from, respectively toward x. Bounded-excess flows suggest a generalization of Circular nowhere-zero flows (cnzf), which can be regarded as (r, 0)-flows. We define (r, α) as Stronger or equivalent to (s, β), if the existence of an (r, α)-flow in a cubic graph always implies the existence of an (s, β)-flow in the same graph. We then study the structure of the bounded-excess flow strength poset. Among other results, we define the Trace of a point in the r − α plane by $tr\left(r,\alpha \right)=\frac{r-2\alpha }{1-\alpha }$ and prove that among points with the same trace the stronger is the one with the smaller α (and larger r). For example, if a cubic graph admits a k-nzf (trace k with α = 0), then it admits an $(r,\frac{k-r}{k-2})$-flow for every r, 2 ≤ r ≤ k. A significant part of the article is devoted to proving the main result: Every cubic graph admits a $(3\frac{1}{2},\frac{1}{2})$-flow, and there exists a graph which does not admit any stronger bounded-excess flow. Notice that $tr(3\frac{1}{2},\frac{1}{2})=5$ so it can be considered a step in the direction of the 5-flow Conjecture. Our result is the best possible for all cubic graphs while the seemingly stronger 5-flow Conjecture relates only to bridgeless graphs. We also show that if the circular-flow number of a cubic graph is strictly less than 5, then it admits a $(3\frac{1}{3},\frac{1}{3})$-flow (trace 4). We conjecture such a flow to exist in every cubic graph with a perfect matching, other than the Petersen graph. This conjecture is a stronger version of the Ban-Linial Conjecture [1]. Our work here strongly relies on the notion of Orientable k-weak bisections, a certain type of k-weak bisections. k-Weak bisections are defined and studied by L. Esperet, G. Mazzuoccolo, and M. Tarsi [4].     

Numbers of cubic graphs

The numbers of unlabeled cubic graphs on p = 2n points have been found by two different counting methods, the best of which has given values for p ≦ 40.     

Decomposing planar cubic graphs

The 3‐Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2‐regular subgraph and a matching. We show that this conjecture holds for the class of connected plane cubic graphs.     

Gromov hyperbolic cubic graphs

If X is a geodesic metric space and x ₁; x ₂; x ₃ ∈ X, a geodesic triangle T = {x ₁; x ₂; x ₃} is the union of the three geodesics [x ₁ x ₂], [x ₂ x ₃] and [x ₃ x ₁] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by δ(X) the sharp hyperbolicity constant of X, i.e., δ(X) = inf {δ ≥ 0: X is δ-hyperbolic}. We obtain information about the hyperbolicity constant of cubic graphs (graphs with all of their vertices of degree 3), and prove that for any graph G with bounded degree there exists a cubic graph G* such that G is hyperbolic if and only if G* is hyperbolic. Moreover, we prove that for any cubic graph G with n vertices, we have δ(G) ≤ min {3n/16 + 1; n/4}. We characterize the cubic graphs G with δ(G) ≤ 1. Besides, we prove some inequalities involving the hyperbolicity constant and other parameters for cubic graphs.     

On disjoint matchings in cubic graphs

For $i=2,3$ and a cubic graph $G$ let ${\nu }_i\left(G\right)$ denote the maximum number of edges that can be covered by $i$ matchings. We show that ${\nu }_2\left(G\right)\ge \frac{4}{5}\left|V\left(G\right)\right|$ and ${\nu }_3\left(G\right)\ge \frac{7}{6}\left|V\left(G\right)\right|$. Moreover, it turns out that ${\nu }_2\left(G\right)\le \frac{\left|V\left(G\right)\right|+2{\nu }_3\left(G\right)}{4}$.     

Change graphs of edge-colorings of planar cubic graphs

It will be proved that the number of vertices of each component of the change-graph of two edge-colorings of an arbitrary planar cubic graph is even (here a change-graph is the subgraph containing exactly those edges having different colors in the considered two edge-colorings and moreover only those vertices which are incident with at least one of these edges).     

The toughness of cubic graphs

The toughness of a graphG is the minimum of|S|/k(G – S) over all setsS of vertices such thatk(G – S) 2. In this paper upper bounds on the toughness of a cubic graph are derived in terms of the independence number and coloring parameters. These are applied to cycle permutation graphs.     

Counting labeled general cubic graphs

Recurrence relations are derived for the numbers of labeled 3-regular graphs with given connectivity, order, number of double edges, and number of loops. This work builds on methods previously developed by Read, Wormald, Palmer, and Robinson.     

Rainbowness of cubic plane graphs

The rainbowness, rb(G), of a connected plane graph G is the minimum number k such that any colouring of vertices of the graph G using at least k colours involves a face all vertices of which receive distinct colours. For a connected cubic plane graph G we prove that

     

Fast generation of cubic graphs

In this paper an efficient algorithm to generate regular graphs with small vertex valency is presented. The running times of a program based on this algorithm and designed to generate cubic graphs are below two natural benchmarks: (a) If N(n) denotes the number of pairwise non-isomorphic cubic graphs with n vertices and T(n) the time needed for generating the list of all these graphs, then T(n)/N(n) decreases gradually for the observed values of n. This suggests that T(n)/N(n) might be uniformly bounded for all n, ignoring the time to write the outputs, but we are unable to prove this and in fact are not confident about it. (b) For programs that generate lists of non-isomorphic objects, but cannot a priori make sure to avoid the generation of isomorphic copies, the time needed to check a randomly ordered list of these objects for being non-isomorphic is a natural benchmark. Since for large lists (n ≥ 22, girth 3) existing graph isomorphism programs take longer to canonically label all of the N(n) graphs than our algorithm takes to generate them, our algorithm is probably faster than any method which does one or more isomorphism test for every graph. © 1996 John Wiley & Sons, Inc.     

Bipartite density of cubic graphs

We first obtain the exact value for bipartite density of a cubic line graph on n vertices. Then we give an upper bound for the bipartite density of cubic graphs in terms of the smallest eigenvalue of the adjacency matrix. In addition, we characterize, except in the case n=20, those graphs for which the upper bound is obtained.     

On isomorphic linear partitions in cubic 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. It is well known that la(G)=2 when G is a cubic graph and Wormald [N. Wormald, Problem 13, Ars Combinatoria 23(A) (1987) 332-334] conjectured that if |V(G)|≡0 (mod 4), then it is always possible to find a linear partition in two isomorphic linear forests. Here, we give some new results concerning this conjecture.