Displaying similar documents to “Connectivity of path graphs.”

Path-Neighborhood Graphs

R.C. Laskar, Henry Martyn Mulder (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A path-neighborhood graph is a connected graph in which every neighborhood induces a path. In the main results the 3-sun-free path-neighborhood graphs are characterized. The 3-sun is obtained from a 6-cycle by adding three chords between the three pairs of vertices at distance 2. A Pk-graph is a path-neighborhood graph in which every neighborhood is a Pk, where Pk is the path on k vertices. The Pk-graphs are characterized for k ≤ 4.

The Path-Distance-Width of Hypercubes

Yota Otachi (2013)

Discussiones Mathematicae Graph Theory

Similarity:

The path-distance-width of a connected graph G is the minimum integer w satisfying that there is a nonempty subset of S ⊆ V (G) such that the number of the vertices with distance i from S is at most w for any nonnegative integer i. In this note, we determine the path-distance-width of hypercubes.

Diameter in path graphs.

Belan, A., Jurica, P. (1999)

Acta Mathematica Universitatis Comenianae. New Series

Similarity:

Heavy subgraph pairs for traceability of block-chains

Binlong Li, Hajo Broersma, Shenggui Zhang (2014)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o−1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least n−1 in G. A block-chain is a graph whose block graph is a path, i.e., it is either a P1, P2, or a 2-connected graph, or a graph with at least one cut vertex and exactly two...