Displaying similar documents to “The contractible subgraph of 5 -connected graphs”

Contractible edges in some k -connected graphs

Yingqiu Yang, Liang Sun (2012)

Czechoslovak Mathematical Journal

Similarity:

An edge e of a k -connected graph G is said to be k -contractible (or simply contractible) if the graph obtained from G by contracting e (i.e., deleting e and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still k -connected. In 2002, Kawarabayashi proved that for any odd integer k ≥ 5 , if G is a k -connected graph and G contains no subgraph D = K 1 + ( K 2 ∪ K 1 , 2 ) , then G has a k -contractible edge. In this paper, by generalizing this result, we prove that...

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.

Connected resolvability of graphs

Varaporn Saenpholphat, Ping Zhang (2003)

Czechoslovak Mathematical Journal

Similarity:

For an ordered set W = { w 1 , w 2 , ⋯ , w k } of vertices and a vertex v in a connected graph G , the representation of v with respect to W is the k -vector r ( v | W ) = ( d ( v , w 1 ) , d ( v , w 2 ) , ⋯ , d ( v , w k ) ) , where d ( x , y ) represents the distance between the vertices x and y . The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W . A resolving set for G containing a minimum number of vertices is a basis for G . The dimension dim ( G ) is the number of vertices in a basis for G . A resolving set W of G is connected...