An open problem: (4; g)-cages with odd g <= 5 are tightly connected

Tang, J., Balbuena, C., Lin, Y. and Miller, M.

Interconnection networks form an important area which has received much attention, both in theoretical research and in practice. From theoretical point of view, an interconnection network can be modelled by a graph, where the vertices of the graph represent the nodes of the network and the edges of the graph represent connections between the nodes in the network. Fault tolerance is an important performance feature when designing a network, and the connectivity of the underlying graph is one of the measures of fault tolerance for a network. A graph is connected if there is a path between any two vertices of G. We say that G is t-connected if the deletion of at least t vertices of G is required to disconnect the graph. A graph with minimum degree \delta\ is maximally connected if it is \delta\-connected. A graph is superconnected if its only minimum disconnecting sets are those induced by the neighbors of a vertex; a graph is said to be tightly superconnected if (i) any minimum disconnecting set is the set of neighbors of a single vertex; and (ii) the deletion of a minimum disconnecting set results in a graph with two components (one of which has only one vertex, another component is a connected graph). A (\delta\; g) - cage is a \delta\-regular graph with girth g and with the least possible number of vertices. In this paper we consider the problem of whether or not (4; g)-cages for g >= 5 are tightly superconnected. We present some partial results and the remaining open problems.

Cite as: Tang, J., Balbuena, C., Lin, Y. and Miller, M. (2007). An open problem: (4; g)-cages with odd g <= 5 are tightly connected. In Proc. Thirteenth Computing: The Australasian Theory Symposium (CATS2007), Ballarat, Australia. CRPIT, 65. Gudmundsson, J. and Jay, B., Eds. ACS. 141-144.

(from crpit.com) (local if available)