
Let \(G\) be a graph. A cutset \(S\) of \(G\) is tight if \(|S|=c(G-S)\). The authors define a reduction step in \(G\) to be the deletion of all edges joining two vertices that lie together in a tight cutset, making each tight cutset independent. The (Hamiltonian) reduction \(R(G)\) of a 1-tough graph \(G\) is the iterative application of reduction steps until the remaining graph has no non-independent tight cutsets. They show that a graph \(G\) is Hamiltonian if and only if its reduced graph \(R(G)\) is Hamiltonian, and they construct 1-tough graphs \(G\) such that \(R(G)\) is not 1-tough, which implies that \(G\) is not Hamiltonian. The authors also define a procedure of adding edges. When a graph \(G\) has a tight cutset \(S\), the graph obtained from \(G\) by filling \(S\) is the supergraph of \(G\) obtained by adding edges to make the vertices of \(S\) pairwise adjacent. A maximal filling of \(G\) is a graph obtained by iteratively filling tight cutsets until every remaining tight cutset induces a complete subgraph. They show that a sufficient condition for a graph \(G\) to be Hamiltonian is that the Hamiltonian closure of some maximal filling of \(G\) is complete, and they construct graphs \(G\) whose Hamiltonian closure is not complete but filling a tight cutset in the graph yields a graph whose Hamiltonian closure is complete. Lastly, the authors characterize some structures of tight cutsets in \(G\) when \(G\) is Hamiltonian.
Eulerian and Hamiltonian graphs, Hamiltonian cycle, toughness, Density (toughness, etc.), spanning cycle, Hamiltonian closure
Eulerian and Hamiltonian graphs, Hamiltonian cycle, toughness, Density (toughness, etc.), spanning cycle, Hamiltonian closure
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
