Displaying similar documents to “The all-paths transit function of a graph”

A simple proof of Whitney's Theorem on connectivity in graphs

Kewen Zhao (2011)

Mathematica Bohemica

Similarity:

In 1932 Whitney showed that a graph G with order n ≥ 3 is 2-connected if and only if any two vertices of G are connected by at least two internally-disjoint paths. The above result and its proof have been used in some Graph Theory books, such as in Bondy and Murty’s well-known Graph Theory with Applications. In this note we give a much simple proof of Whitney’s Theorem.

Containers and wide diameters of P 3 ( G )

Daniela Ferrero, Manju K. Menon, A. Vijayakumar (2012)

Mathematica Bohemica

Similarity:

The P 3 intersection graph of a graph G has for vertices all the induced paths of order 3 in G . Two vertices in P 3 ( G ) are adjacent if the corresponding paths in G are not disjoint. A w -container between two different vertices u and v in a graph G is a set of w internally vertex disjoint paths between u and v . The length of a container is the length of the longest path in it. The w -wide diameter of G is the minimum number l such that there is a w -container of length at most l between any pair...

The forcing geodetic number of a graph

Gary Chartrand, Ping Zhang (1999)

Discussiones Mathematicae Graph Theory

Similarity:

For two vertices u and v of a graph G, the set I(u, v) consists of all vertices lying on some u-v geodesic in G. If S is a set of vertices of G, then I(S) is the union of all sets I(u,v) for u, v ∈ S. A set S is a geodetic set if I(S) = V(G). A minimum geodetic set is a geodetic set of minimum cardinality and this cardinality is the geodetic number g(G). A subset T of a minimum geodetic set S is called a forcing subset for S if S is the unique minimum geodetic set containing T. The forcing...

Paths with restricted degrees of their vertices in planar graphs

Stanislav Jendroľ (1999)

Czechoslovak Mathematical Journal

Similarity:

In this paper it is proved that every 3 -connected planar graph contains a path on 3 vertices each of which is of degree at most 15 and a path on 4 vertices each of which has degree at most 23 . Analogous results are stated for 3 -connected planar graphs of minimum degree 4 and 5 . Moreover, for every pair of integers n ≥ 3 , k ≥ 4 there is a 2 -connected planar graph such that every path on n vertices in it has a vertex of degree k .