Displaying 621 – 640 of 1336

Showing per page

On properties of a graph that depend on its distance function

Ladislav Nebeský (2004)

Czechoslovak Mathematical Journal

If G is a connected graph with distance function d , then by a step in G is meant an ordered triple ( u , x , v ) of vertices of G such that d ( u , x ) = 1 and d ( u , v ) = d ( x , v ) + 1 . A characterization of the set of all steps in a connected graph was published by the present author in 1997. In Section 1 of this paper, a new and shorter proof of that characterization is presented. A stronger result for a certain type of connected graphs is proved in Section 2.

On properties of maximal 1-planar graphs

Dávid Hudák, Tomáš Madaras, Yusuke Suzuki (2012)

Discussiones Mathematicae Graph Theory

A graph is called 1-planar if there exists a drawing in the plane so that each edge contains at most one crossing. We study maximal 1-planar graphs from the point of view of properties of their diagrams, local structure and hamiltonicity.

On r -extendability of the hypercube Q n

Nirmala B. Limaye, Dinesh G. Sarvate (1997)

Mathematica Bohemica

A graph having a perfect matching is called r -extendable if every matching of size r can be extended to a perfect matching. It is proved that in the hypercube Q n , a matching S with | S | n can be extended to a perfect matching if and only if it does not saturate the neighbourhood of any unsaturated vertex. In particular, Q n is r -extendable for every r with 1 r n - 1 .

On radially extremal digraphs

Ferdinand Gliviak, Martin Knor (1995)

Mathematica Bohemica

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.

On rainbow connection.

Caro, Yair, Lev, Arie, Roditty, Yehuda, Tuza, Zsolt, Yuster, Raphael (2008)

The Electronic Journal of Combinatorics [electronic only]

Currently displaying 621 – 640 of 1336