Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs

Binlong Li;  Hajo J. Broersma;  Shenggui Zhang — 2016

Discussiones Mathematicae Graph Theory

A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K1 ∪ P4 as the only open case.

Heavy cycles in weighted graphs

J. Adrian Bondy;  Hajo J. Broersma;  Jan van den Heuvel;  Henk Jan Veldman — 2002

Discussiones Mathematicae Graph Theory

An (edge-)weighted graph is a graph in which each edge e is assigned a nonnegative real number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges, and an optimal cycle is one of maximum weight. The weighted degree w(v) of a vertex v is the sum of the weights of the edges incident with v. The following weighted analogue (and generalization) of a well-known result by Dirac for unweighted graphs is due to Bondy and Fan. Let G be a 2-connected weighted graph such...

Page 1

Download Results (CSV)