The square of every two-connected graph is Hamiltonian |
| |
Authors: | Herbert Fleischner |
| |
Institution: | Department of Mathematics, State University of New York at Binghamton, Binghamton, New York 13901, USA |
| |
Abstract: | A graph G is a line-critical block if κ(G) = 2 and if for any line e of G the graph G ? e has κ(G ? e) = 1.If G is a line-critical block, then G is either a DT-block (i.e., G is a two-connected graph in which every line is incident to a point of degree two), or G contains a specific two-connected subgraph which is a DT-block (Theorem 1). Using this result and results of the preceding paper on DT-graphs, a simple proof of the conjecture that the square of every two-connected graph is Hamiltonian is given. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|