An (r,z,k)-mixed graph G has every vertex with undirected degree r, directed in- and out-degree z, and diameter k. In this paper, we study the case r = z = 1, proposing some new constructions of (1,1,k)-mixed graphs with a large number of vertices N. Our study is based on computer techniques for small values of k and the use of graphs on alphabets for general k. In the former case, the constructions are either Cayley or lift graphs. In the latter case, some infinite families of (1,1,k)-mixed graphs are proposed with diameter of the order of 2log2 N.

Abstract For graphs with maximum degree d and diameter k, an upper bound on the number of vertices in the graphs is provided by the well‐known Moore bound (denoted by Md,k). Graphs that achieve this bound (Moore graphs) are very rare, and determining how close one can come to the Moore bound has been a major topic in graph theory. Of particular note in this regard are the cage problem and the degree/diameter problem. In this article, we take a different approach and consider questions that arise when we fix the number of vertices in the graph at the Moore bound, but relax, by one, the diameter constraint on a subset of the vertices. In this context, regular graphs of degree d, radius k, diameter k + 1, and order equal to Md,k are called radially Moore graphs. We consider two specific questions. First, we consider the existence question (extending the work of Knor), and second, we consider some natural measures of how well a radially Moore graph approximates a Moore graph. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010

The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. Their motivation for identification came from finding malfunctioning processors in multiprocessor systems. Besides that identifying codes can also be applied to sensor networks. In this paper we consider identifying codes in Hamming spaces. We first concentrate on improving the lower bounds on codes which identify words within distance r > 1. These improvements are achieved using a new approach. Then we proceed by introducing new lower bounds on codes identifying sets of words. Constructions for such codes with the best known cardinalities are also given.

In binary Hamming spaces, we construct new 1- identifying codes which improve on previously known upper bounds on the cardinalities of 1-identifying codes for many lengths when n ges 10. We also construct tau-identifying codes using the direct sum of tau codes that are 1-identifying.

In binary Hamming spaces, we construct new$1$-identifying codes from$2$-fold$1$-coverings that are$1$-identifying. We improve on previously known upper bounds for the cardinalities of$1$-identifying codes of many lengths when$n\geq 10$. We construct$t$-identifying codes using the direct sum of$t$$1$-identifying codes. This solves partly an open problem posed by Blass, Honkala, and Litsyn in 2001. We also prove a general result concerning the direct sum of a$t$-identifying code with the whole space of any dimension.

New lower bounds are given for the classical Ramsey numbers $R (3,10)$ and $R (3,12)$. Both constructions were made using a variant of the Metropolis Algorithm and were built on smaller cyclic constructions.

Abstract A measure of communication network vulnerability was studied in a recent article by Boesch, Harary, and Kabell. The persistence (line persistence) is the minimum number of points (lines) whose removal from a graph increases its diameter. Their approach differed from earlier work on this topic in that they examined the analogs of Menger's theorem for these invariants. A result of Lovász, Neumann‐Lara, and Plummer is used to prove modified versions of their theorems (the original proofs are incorrect). Some related problems are also solved, including one posed by Hartman and Rubin.

Abstract The linear arboricity of a graph is the minimum number of linear forests into which its lines can be decomposed. We find that the linear arboricity of every 4‐regular graph is 3. This result enables us to obtain bounds for the linear arboricity of any graph in terms of its maximum degree.