Smallest Regular Graphs of Given Degree and Diameter
In this note we present a sharp lower bound on the number of vertices in a regular graph of given degree and diameter.
Minimal non-selfcentric radially-maximal graphs of radius 4
There is a hypothesis that a non-selfcentric radially-maximal graph of radius r has at least 3r-1 vertices. Using some recent results we prove this hypothesis for r = 4.
Gray codes in graphs
Note on linear arboricity
Connectivity of path graphs
We prove a necessary and sufficient condition under which a connected graph has a connected P₃-path graph. Moreover, an analogous condition for connectivity of the Pₖ-path graph of a connected graph which does not contain a cycle of length smaller than k+1 is derived.
Radii and centers in iterated line digraphs
We show that the out-radius and the radius grow linearly, or "almost" linearly, in iterated line digraphs. Further, iterated line digraphs with a prescribed out-center, or a center, are constructed. It is shown that not every line digraph is admissible as an out-center of line digraph.
On radially extremal digraphs
We define digraphs minimal, critical, and maximal by three types of radii. Some of these classes are completely characterized, while for the others it is shown that they are large in terms of induced subgraphs.
Graphs isomorphic to their path graphs
We prove that for every number , the -iterated -path graph of is isomorphic to if and only if is a collection of cycles, each of length at least 4. Hence, is isomorphic to if and only if is a collection of cycles, each of length at least 4. Moreover, for we reduce the problem of characterizing graphs such that to graphs without cycles of length exceeding .
Centers in line graphs
Two-radially maximal graphs with special centers
Biembeddings of symmetric configurations and 3-homogeneous Latin trades
Using results of Altshuler and Negami, we present a classification of biembeddings of symmetric configurations of triples in the torus or Klein bottle. We also give an alternative proof of the structure of 3-homogeneous Latin trades.
Page 1