The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “A Sufficient Condition for Graphs to Be SuperK-Restricted Edge Connected”

The contractible subgraph of 5 -connected graphs

Chengfu Qin, Xiaofeng Guo, Weihua Yang (2013)

Czechoslovak Mathematical Journal

Similarity:

An edge e of a k -connected graph G is said to be k -removable if G - e is still k -connected. A subgraph H of a k -connected graph is said to be k -contractible if its contraction results still in a k -connected graph. A k -connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k -connected. In this paper, we show that there is a contractible subgraph in a 5 -connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex...

Graphs with rainbow connection number two

Arnfried Kemnitz, Ingo Schiermeyer (2011)

Discussiones Mathematicae Graph Theory

Similarity:

An edge-coloured graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow connected. In this paper we prove that rc(G) = 2 for every connected graph G of order n and size m, where n - 1 2 + 1 ≤ m ≤ n 2 - 1 . We also characterize graphs with rainbow connection number two and large clique number.

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...

The crossing number of the generalized Petersen graph P [ 3 k , k ]

Stanley Fiorini, John Baptist Gauci (2003)

Mathematica Bohemica

Similarity:

Guy and Harary (1967) have shown that, for k ≥ 3 , the graph P [ 2 k , k ] is homeomorphic to the Möbius ladder M 2 k , so that its crossing number is one; it is well known that P [ 2 k , 2 ] is planar. Exoo, Harary and Kabell (1981) have shown hat the crossing number of P [ 2 k + 1 , 2 ] is three, for k ≥ 2 . Fiorini (1986) and Richter and Salazar (2002) have shown that P [ 9 , 3 ] has crossing number two and that P [ 3 k , 3 ] has crossing number k , provided k ≥ 4 . We extend this result by showing that P [ 3 k , k ] also has crossing number k for all k ≥ 4 .

The eavesdropping number of a graph

Jeffrey L. Stuart (2009)

Czechoslovak Mathematical Journal

Similarity:

Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v , a minimum { u , v } -separating set is a smallest set of edges in G whose removal disconnects u and v . The edge connectivity of G , denoted λ ( G ) , is defined to be the minimum cardinality of a minimum { u , v } -separating set as u and v range over all pairs of distinct vertices in G . We introduce and investigate the eavesdropping number, denoted ε ( G ) , which is defined to be the maximum cardinality...