Onk-Critical Connected Line Graphs

✍ Scribed by Matthias Kriesell

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 181 KB
• Volume: 74
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1998.1823

✦ Synopsis

We show that any line graph contains a set of three vertices which is not included in a smallest separating vertex set. This was conjectured by Maurer and Slater.

1998 Academic Press

Let }(G) denote the vertex connectivity of a graph G. A set of }(G) vertices which separates G will be called a smallest separating set of G and the set of all smallest separating sets will be denoted by

this was conjectured by Slater in [4] and proved by Su in . Earlier, Hamidoune proved this conjecture for line graphs . We shall prove that k 2 if G is a k-critical line graph.

An edge connecting two vertices x and y of a graph G=(V, E) will be denoted by [x, y].

The index G will be left out if it is clear from the context. G(X) denotes the subgraph of G induced by the vertex set X V(G). We call X connected if G(X) is connected and we call X complete if G(X ) is complete. K n denotes the complete graph on n vertices. An induced subgraph of G on four vertices is a claw of G if it contains one vertex of degree 3 and three of degree 1.

P(M ) denotes the power set of a set M. Let S P(V(G)). Let T # T G and suppose S T for some S # S. The union of at least one but not of all components of G&T is called a T&S-fragment of G. An S-fragment is a T&S-fragment for a T # T G . For each T&S-fragment F we define the T&S-fragment F by F :=G&(T _ F). An S-fragment of minimum cardinality is called an S-atom of G, a T&S-atom A is an S-atom with N(A)=T. In case of S=[<] we omit the reference to S.

Repeating the definition of [3], we call G S-critical if S{<, for each S # S there is a T # T G with S T, and for each T&S-fragment F Article No. TB981823