ATOMS OF CYCLIC CONNECTIVITY IN REGULAR GRAPHS

Justin Wiser

ABSTRACT: We will examine various properties of atoms of cyclic connectivity in finite, connected, regular graphs. We obtain several results generalizing those of Nedela and Skoviera [1]. There are two main results of this paper. We arrive at an exhaustive list of regular graphs with no disjoint cycles. We also relate the valence and girth of a regular graph to its cyclic connectivity, finding a precise equality if and only if there are no nontrivial proper atoms.

I. Definitions and Notations

Let G =(V, E) be a connected graph. A cycle separating edge cutwill be a subset of E such that G – E is disconnected where at least two connected components of G – E contain a cycle. We say that G is cyclically k-edge-connected if no cycle separating edge cut in G contains fewer than k edges. We will denote by (G), the largest integer, k, not exceeding the Betti Number of G, (G), such that G is cyclically k-edge-connected. This is called the cyclic edge connectivity of G. We shall, however, simply refer to it as the cyclic connectivity of G. Note that (G) = (G) iff G has no cycle separating edge cuts.

Given any subgraph, X, of G, let δX denote the set of edges in G with exactly one vertex in X. We will call X a cyclic part of G if δX is a cycle separating edge cut and X is minimally cyclically connected (ie: |δX| = (G) ). A cyclic part that is minimal under inclusion will be called an atom of G. Atoms which are cycles are called trivial. Atoms with a minimal number of vertices are called proper. We will also denote by X, the subgraph of G induced by the vertices V\V(X).

I will denote by Tn, the n-regular, looplessmultigraph on 2 vertices. I will denote by n, the graph obtained from C3, by replicating every edge n times. Specifically, if e  E(C3), then n distinct copies of e are in E(n).

II. Results

We will start by classifying graphs containing a girth cycle that is disjoint from all other cycles. We will employ the method used by Nedela and Skoviera [1].

From now on, we will restrict our attention to finite, connected, regular graphs.

PROPOSITION 1: Let G be a finite, connected, 4-regular graph of girth = g. Suppose that G contains a girth cycle, C, such that C is a forest. Then, G is isomorphic to one of: T4, 2, or K5.

Proof: Since C is a forest, it is clear that exactly one of the following 3 cases must hold: 1) C is empty, or 2) C is non-empty and contains only isolated vertices, or 3) C is non-empty and contains 2 vertices of unit valence.

Suppose that C is empty. In this case, all of the vertices of G are contained in C.

Consider the circumstance g = |C| = |G| > 2. In this case, adding any edge to C would create a cycle strictly shorter than C. Since G is 4-regular, edges must be added to C. We arrive at a contradiction since C was a girth cycle by hypothesis. Hence, we must have g=2 and G  T4.

Suppose that Cis non-empty and consists only of isolated vertices. Let u be an isolated vertex in C. We see that u must be adjacent to 4 vertices in C. At least 2 of these vertices, x and y, must have d(x, y)  g/4 in C. Thus, there is a closed cycle in g of length, L  g/4 + 2. Therefore, g  g/4 + 2 and g must take on the value 2. So, |δC| = 4 and it follows that u is the only isolated vertex contained in C. Thus, G 2.

Suppose now that C contains 2 vertices of valency 1. Each of these vertices is adjacent to 3 vertices in C. Thus, a cycle must exist of length, L  g/3+2. Hence,

g  g/3+2 and g must take on the value of 2 or 3. If g=2, |δC| = 4, but |δC|  6 because C has two 1-valent vertices. Thus, g=3, |δC| = 6, C K2, and G  K5. 

PROPOSITION 2: Let G be a finite, connected, n-regular graph of girth = g, with n > 4. Suppose that G contains a girth cycle, C, such that C is a forest. Then, G is isomorphic to Tn.

Proof: We consider the same 3 cases as in Proposition 1. If C is empty, we find via the same argument that G Tn. If C contains k isolated vertices, we arrive at the inequality g  g/n + 2  g/5 + 2 and thus g=2 and |δC| = 2(n-2). However, we must have that |δC| = kn = 2n-4 which is a contradiction because n>4 by hypothesis. If C has two 1-valent vertices, then g  g/(n-1) + 2  g/4 + 2. Thus, g=2 and |δC| = 2(n-2). But, since there are two 1-valent vertices, we must have that |δC|  2(n-1), a contradiction. 

We also cite the result that if G is a finite, connected, cubic graph containing a girth cycle, C, such that C is a forest, then G  K4, K3,3,or 2. [1]

Observe that if G is a finite, connected, regular graph containing a girth cycle, C, and C is a forest, then G has no disjoint cycles. (None of the graphs listed contain disjoint cycles.) Moreover, if G has no disjoint cycles then C must be a forest. Therefore, we have arrived at an exhaustive list of all finite, regular, connected graphs without disjoint cycles (without cycle separating edge cuts).

PROPOSITION 3: Let G be a finite, connected, n-regular graph of girth=g.

(G) = (n-2)g if and only if there are no nontrivial, proper atoms and G is not isomorphic to Tn with n>4.

Proof: First, note that Nedela and Skoviera [1] proved this result in the case where n=3. This is a direct generalization of that proof. We will now suppose n>3.

Suppose (G) = (n-2)g, and G contains a nontrivial, proper atom, A. Clearly, G is not isomorphic to any of the special cases from the first two propositions. Thus, if we take C to be a girth cycle of G, then δC must be a cycle separating edge cut. We see that|δC| = (n-2)g = (G) so clearly, C is an atom. Thus, |A|  |C| = g because A is proper. But, A properly contains a cycle. Thus, we must have g < |A|, a contradiction.

Suppose that G has no nontrivial, proper atoms. If G is a special case listed in Proposition 1 or 2, then it is trivial to calculate that (G) = (G) = |E| - |V| + 1 = (n-2)g except in the case where G=Tn. If G is not one of the special cases, then G has disjoint cycles and thus G has proper atoms, all of which must be trivial. Let C be any proper atom in G. Then, (G) = (n-2)|C|  (n-2)g. But it is obvious that for any finite, connected, regular graph, (G)  (n-2)g. Therefore, (G) = (n-2)g, completing the proof. 

Note that since it is always true that (G)  (n-2)g, it must be the case that

(G) < (n-2)g when equality does not hold. With this in mind, there is one remaining atomic structural result that follows immediately from Proposition 3.

COROLLARY: In a finite, connected, regular graph, either all proper atoms are trivial or all proper atoms are non-trivial, or there are no atoms.

Proof: Let G be a finite, connected, regular graph containing atoms. Suppose G contains a trivial proper atom, C, and a nontrivial proper atom. We conclude that

(G) = (n-2)|C|  (n-2)g and (G) < (n-2)g, respectively, a contradiction. 

Given the above corollary, it is easy to see that there is not a lot of freedom in the atomic structure of a finite, connected, regular graph. If there exists a single trivial atom, it is necessarily a girth cycle. Thus, it must be proper as any atom must contain a cycle. Therefore, via the above corollary, every proper atom must be trivial. Therefore, every finite connected regular graph satisfies exactly one of the following cases:

A)Every atom is nontrivial.

B)Proper atoms are trivial (necessarily girth cycles) and the improper atoms, if they exist, are all nontrivial.

III. Discussion

For finite, connected, cubic graphs, Nedela and Skoviera have shown that vertex transitive graphs [1] and edge transitive graphs [2] cannot have nontrivial proper atoms and thus, the equality (G) = g must hold. I have been unable, as of yet, to find a similar transitivity relationship in higher valence cases. There is a known counterexample if only vertex transitivity is used. C4[K2] is a vertex transitive (not edge transitive) graph with a nontrivial, proper atom. However, the equality may follow from edge transitivity or arc transitivity.

It is still an open problem to rule out Case A, above, for large classes of graphs (such as those with a transitivity property).

REFERENCES

[1] NEDELA, R. – SKOVIERA, M. : Atoms of Cyclic Connectivity in Cubic Graphs, Math. Slovaca, 45 (1995), No. 5, 481-499.

[2] NEDELA, R. – SKOVIERA, M. : Atoms of Cyclic Connectivity in Transitive Cubic Graphs.

In: Contemporary Methods in Graph Theory (R. Bodendeik, ed.), BI-Weissenschaftsverlag, Mannheim, 1990, pp. 479-488.