# Search Results

## Abstract

A vertex cut of a connected graph G is a set of vertices whose deletion disconnects G. A connected graph G is super-connected if the deletion of every minimum vertex cut of G isolates a vertex. The super-connectivity is the size of the smallest vertex cut of G such that each resultant component does not have an isolated vertex. The Kneser graph KG(n, k) is the graph whose vertices are the k-subsets of {1, 2, . . . , n} and two vertices are adjacent if the k-subsets are disjoint. We use Baranyai’s Theorem on the decompositions of complete hypergraphs to show that the Kneser graph KG are super-connected when n ≥ 5 and that their super-connectivity is n ( n/2) − 6 when n ≥ 6.

## Abstract

A nut graph is a singular graph with one-dimensional kernel and corresponding eigenvector with no zero elements. The problem of determining the orders *n* for which *d*-regular nut graphs exist was recently posed by Gauci, Pisanski and Sciriha. These orders are known for *d ≤* 4. Here we solve the problem for all remaining cases *d ≤* 11 and determine the complete lists of all *d*-regular nut graphs of order *n* for small values of *d* and *n*. The existence or non-existence of small regular nut graphs is determined by a computer search. The main tool is a construction that produces, for any *d*-regular nut graph of order *n*, another *d*-regular nut graph of order *n*+2*d*. If we are given a sufficient number of *d*-regular nut graphs of consecutive orders, called seed graphs, this construction may be applied in such a way that the existence of all *d*-regular nut graphs of higher orders is established. For even *d* the orders *n* are indeed consecutive, while for odd *d* the orders *n* are consecutive even numbers. Furthermore, necessary conditions for combinations of order and degree for vertex-transitive nut graphs are derived.