Displaying similar documents to “Note on the relation between radius and diameter of a graph”

On independent sets and non-augmentable paths in directed graphs

H. Galeana-Sánchez (1998)

Discussiones Mathematicae Graph Theory

Similarity:

We investigate sufficient conditions, and in case that D be an asymmetrical digraph a necessary and sufficient condition for a digraph to have the following property: "In any induced subdigraph H of D, every maximal independent set meets every non-augmentable path". Also we obtain a necessary and sufficient condition for any orientation of a graph G results a digraph with the above property. The property studied in this paper is an instance of the property of a conjecture of J.M. Laborde,...

Radii and centers in iterated line digraphs

Martin Knor, L'udovít Niepel (1996)

Discussiones Mathematicae Graph Theory

Similarity:

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 graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect

Hortensia Galeana-Sánchez, José de Jesús García-Ruvalcaba (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A digraph D is called a kernel-perfect digraph or KP-digraph when every induced subdigraph of D has a kernel. We call the digraph D an m-coloured digraph if the arcs of D are coloured with m distinct colours. A path P is monochromatic in D if all of its arcs are coloured alike in D. The closure of D, denoted by ζ(D), is the m-coloured digraph defined as follows: V( ζ(D)) = V(D), and A( ζ(D)) = ∪_{i} {(u,v) with colour i: there exists a monochromatic...