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

Two operations on a graph preserving the (non)existence of 2-factors in its line graph

Mingqiang An, Hong-Jian Lai, Hao Li, Guifu Su, Runli Tian, Liming Xiong (2014)

Czechoslovak Mathematical Journal

Similarity:

Let G = ( V ( G ) , E ( G ) ) be a graph. Gould and Hynds (1999) showed a well-known characterization of G by its line graph L ( G ) that has a 2-factor. In this paper, by defining two operations, we present a characterization for a graph G to have a 2-factor in its line graph L ( G ) . A graph G is called N 2 -locally connected if for every vertex x ∈ V ( G ) , G [ { y ∈ V ( G ) 1 ≤ dist G ( x , y ) ≤ 2 } ] is connected. By applying the new characterization, we prove that every claw-free graph in which every edge lies on a cycle of length at most five and in which...