High Connectivity Keeping Sets In <Emphasis Type="Italic">n</Emphasis>-Connected Graphs

It is proved that for every positive integer k, every n-connected graph G of sufficiently large order contains a set W of k vertices such that G—W is (n-2)-connected. It is shown that this does not remain true if we add the condition that G(W) is connected.     

Precomplete Clones on Infinite Sets which are Closed under Conjugation

We show that on an infinite set, there exist no other precomplete clones closed under conjugation except those which contain all permutations. Since on base sets of some infinite cardinalities, in particular on countably infinite ones, the precomplete clones containing the permutations have been determined, this yields a complete list of the precomplete conjugation-closed clones in those cases. In addition, we show that there exist no precomplete submonoids of the full transformation monoid which are closed under conjugation except those which contain the permutations; the monoids of the latter kind are known.     

On Closed Weingarten Surfaces

We investigate closed surfaces in Euclidean 3-space satisfying certain functional relations κ = F(λ) between the principal curvatures κ, λ. In particular we find analytic closed surfaces of genus zero where F is a quadratic polynomial or F(λ) = cλ²ⁿ⁺¹. This generalizes results by H. Hopf on the case where F is linear and the case of ellipsoids of revolution where F(λ) = cλ³.     

Sets pooling designs

Pooling desings have previously been used for the efficient identification of distinguished elements of a finite setU. Group testing underlies these designs: For any , a binary result is obtainable, indicating whether or not the number of distinguished elements included inS is zero. The current generalization of pooling designs will enable the efficient identification of distinguished subsets of a finite setU. In this case, for any , a binary result is obtainable, indicating whether or not the number of distinguished subsets included inS is zero. Such designs are called sets pooling designs, comprising standard pooling designs in the special case where all the distinguished subsets are elements. The new designs are similar to the standard designs but are subject to new constraints because the set of subsets included inS is its power set. To illustrate the feasibility of constructing sets pooling designs, random, non-adaptive designs are investigated for the special case where all distinguished subsets have the same size. An optimum probability for including an object in a pool is approximated as a function of the size and number of distinguished subsets, adopting the criterion of minimizing the average number of non-distinguished subsets whose status would not be resolved by the pooling design. Deterministic and adaptive designs are also described.This work was supported by the US Department of Energy under contract W-7405-ENG-36, through a Laboratory Directed Research and Development Grant at Los Alamos National Laboratory.     

Edges not contained in triangles and the distribution of contractible edges in a 4-connected graph

We prove results concerning the distribution of 4-contractible edges in a 4-connected graph G in connection with the edges of G not contained in a triangle. As a corollary, we show that if G is 4-regular 4-connected graph, then the number of 4-contractible edges of G is at least one half of the number of edges of G not contained in a triangle.     

Uniform cyclic edge connectivity in cubic graphs

A cubic graph which is cyclicallyk-edge connected and has the further property that every edge belongs to some cyclick-edge cut is called uniformly cyclicallyk-edge connected(U(k)). We classify theU(5) graphs and show that all cyclically 5-edge connected cubic graphs can be generated from a small finite set ofU(5) graphs by a sequence of defined operations.MATHDAHCOTAGE.AC.NZ     

On an extremal problem related to a theorem of Whitney

A well known theorem of Whitney states that for any graph G,

κ(G)?κ^′(G)?δ(G).     

Contractible edges in triangle-free graphs

An edge of a graph is calledk-contractible if the contraction of the edge results in ak-connected graph. Thomassen [5] proved that everyk-connected graph of girth at least four has ak-contractible edge. In this paper, we study the distribution ofk-contractible edges in triangle-free graphs and show the following: Whenk≧2, everyk-connected graph of girth at least four and ordern≧3k, hasn+(3/2)k ²-3k or morek-contractible edges.     

Decomposition of 3-connected graphs

Cunningham and Edmonds [4[ have proved that a 2-connected graphG has a unique minimal decomposition into graphs, each of which is either 3-connected, a bond or a polygon. They define the notion of a good split, and first prove thatG has a unique minimal decomposition into graphs, none of which has a good split, and second prove that the graphs that do not have a good split are precisely 3-connected graphs, bonds and polygons. This paper provides an analogue of the first result above for 3-connected graphs, and an analogue of the second for minimally 3-connected graphs. Following the basic strategy of Cunningham and Edmonds, an appropriate notion of good split is defined. The first main result is that ifG is a 3-connected graph, thenG has a unique minimal decomposition into graphs, none of which has a good split. The second main result is that the minimally 3-connected graphs that do not have a good split are precisely cyclically 4-connected graphs, twirls (K _3,n for somen3) and wheels. From this it is shown that ifG is a minimally 3-connected graph, thenG has a unique minimal decomposition into graphs, each of which is either cyclically 4-connected, a twirl or a wheel.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University.     

Partition conditions and vertex-connectivity of graphs

It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev ₁, ...,v _n ≠V(G) and for any sequence of positive integersk ₁, ...,k _n such thatk ₁+...+k _n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv ₁, ...,v(n), and the class of the partition containingv _i induces a connected subgraph consisting ofk _i vertices, fori=1, 2, ...,n. Now fix the integersk ₁, ...,k _n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv ₁, ...,v _n ≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.     

On the Toughness of a Graph

Abstract

In this paper, general results on the toughness of a graph are considered. Firstly the link between toughness and connectivity is explored and then results linking toughness and the parameters binding number and integrity are given. Further, the toughness of product graphs is discussed including general results for the lexicographic product. The paper concludes with some observations on toughness and hamiltoni-city.     

Partition of graphs with condition on the connectivity and minimum degree

C. Thomassen and M. Szegedy proved the existence of a functionf(s, t) such that the points of anyf(s, t)-connected graph have a decomposition into two non-empty sets such that the subgraphs induced by them ares-connected andt-connected, respectively. We prove, thatf(s, t) ≦ 4s+4t − 13 and examine a similar problem for the minimum degree.     

Cycles through ten vertices in 3-connected cubic graphs

It is known that there exists a cycle through any nine vertices of a 3-connected cubic graphG. Here we show that if an edge is removed from such a graph, then there is still a cycle through any five vertices. Furthermore, we characterise the circumstances in which there fails to be a cycle through six. As corollaries we are able to prove that a 3-connected cubic graph has a cycle through any specified five vertices and one edge, and to classify the conditions under which it has a cycle through four chosen vertices and two edges. We are able to use the five and six vertex results to show that a 3-connected cubic graph has a cycle which passes through any ten given vertices if and only if the graph is not contractible to the Petersen graph in such a way that the ten vertices each map to a distinct vertex of the Petersen graph.     

Convex Embeddings and Bisections of 3-Connected Graphs1

Given two disjoint subsets T ₁ and T ₂ of nodes in an undirected 3-connected graph G = (V, E) with node set V and arc set E, where and are even numbers, we show that V can be partitioned into two sets V ₁ and V ₂ such that the graphs induced by V ₁ and V ₂ are both connected and holds for each j = 1,2. Such a partition can be found in time. Our proof relies on geometric arguments. We define a new type of convex embedding of k-connected graphs into real space R ^k-1 and prove that for k = 3 such an embedding always exists. ¹ A preliminary version of this paper with title Bisecting Two Subsets in 3-Connected Graphs appeared in the Proceedings of the 10th Annual International Symposium on Algorithms and Computation, ISAAC 99, (A. Aggarwal, C. P. Rangan, eds.), Springer LNCS 1741, 425&ndash;434, 1999.     

The connectivities of locally finite primitive graphs

Let be an infinite, locally finite graph whose automorphism group is primitive on its vertex set. It is shown that the connectivity of cannot equal 2, but all other values 0, 1, 3, 4, ... are possible.     

Cycles through specified vertices of a graph

We prove that ifS is a set ofk−1 vertices in ak-connected graphG, then the cycles throughS generate the cycle space ofG. Moreover, whenk≧3, each cycle ofG can be expressed as the sum of an odd number of cycles throughS. On the other hand, ifS is a set ofk vertices, these conclusions do not necessarily hold, and we characterize the exceptional cases. As corollaries, we establish the existence of odd and even cycles through specified vertices and deduce the existence of long odd and even cycles in graphs of high connectivity.     

A note on fragments of infinite graphs

Results involving automorphisms and fragments of infinite graphs are proved. In particular for a given fragmentC and a vertex-transitive subgroupG of the automorphism group of a connected graph there exists σ≠G such that σ[C] ⊂C. This proves the countable case of a conjecture of L. Babai and M. E. Watkins concerning graphs allowing a vertex-transitive torsion group action. Dedicated to Prof. K. Wagner on his 70^th birthday     

Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs

Tibor Gallai made the following conjecture. LetG be ak-chromatic colour-critical graph. LetL denote the set of those vertices ofG having valencyk−1 and letH be the rest ofV(G). Then the number of components induced byL is not less than the number of components induced byH, providedL ≠ 0. We prove this conjecture in a slightly generalized form. Dedicated to Tibor Gallai on his seventieth birthday     

A new bound for neighbor-connectivity of abelian Cayley graphs

For the notion of neighbor-connectivity in graphs, whenever a vertex is “subverted” the entire closed neighborhood of the vertex is deleted from the graph. The minimum number of vertices whose subversion results in an empty, complete, or disconnected subgraph is called the neighbor-connectivity of the graph. Gunther, Hartnell, and Nowakowski have shown that for any graph, neighbor-connectivity is bounded above by κ. The main result of this paper is a sharpening of the bound for abelian Cayley graphs. In particular, we show by constructing an effective subversion strategy for such graphs, that neighbor-connectivity is bounded above by ⌈δ/2⌉+2. Using a result of Watkins the new bound can be recast in terms of κ to get neighbor-connectivity bounded above by ⌈3κ/4⌉+2 for abelian Cayley graphs.