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

Displaying similar documents to “Two operations on a graph preserving the (non)existence of 2-factors in its line graph”

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

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

Cores and shells of graphs

Allan Bickle (2013)

Mathematica Bohemica

Similarity:

The $k$ -core of a graph $G$ , $C_{k} (G)$ , is the maximal induced subgraph $H \subseteq G$ such that $δ (G) \geq k$ , if it exists. For $k > 0$ , the $k$ -shell of a graph $G$ is the subgraph of $G$ induced by the edges contained in the $k$ -core and not contained in the $(k + 1)$ -core. The core number of a vertex is the largest value for $k$ such that $v \in C_{k} (G)$ , and the maximum core number of a graph, $\hat{C} (G)$ , is the maximum of the core numbers of the vertices of $G$ . A graph $G$ is $k$ -monocore if $\hat{C} (G) = δ (G) = k$ . This paper discusses some basic results on the structure of $k$ -cores and...

Displaying similar documents to “Two operations on a graph preserving the (non)existence of 2-factors in its line graph”

The contractible subgraph of 5 -connected graphs

The eavesdropping number of a graph

Cores and shells of graphs

The contractible subgraph of $5$ -connected graphs