Displaying similar documents to “An Implicit Weighted Degree Condition For Heavy Cycles”

Heavy cycles in weighted graphs

J. Adrian Bondy, Hajo J. Broersma, Jan van den Heuvel, Henk Jan Veldman (2002)

Discussiones Mathematicae Graph Theory

Similarity:

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

A σ₃ type condition for heavy cycles in weighted graphs

Shenggui Zhang, Xueliang Li, Hajo Broersma (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges. The weighted degree d w ( v ) of a vertex v is the sum of the weights of the edges incident with v. In this paper, we prove the following result: Suppose G is a 2-connected weighted graph which satisfies the following conditions: 1. The weighted degree sum of any three independent vertices is at least m; 2. w(xz) = w(yz)...

Hamiltonicity of k -traceable graphs.

Bullock, Frank, Dankelmann, Peter, Frick, Marietjie, Henning, Michael A., Oellermann, Ortrud R., van Aardt, Susan (2011)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

On Vertices Enforcing a Hamiltonian Cycle

Igor Fabrici, Erhard Hexel, Stanislav Jendrol’ (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A nonempty vertex set X ⊆ V (G) of a hamiltonian graph G is called an H-force set of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The H-force number h(G) of a graph G is defined to be the smallest cardinality of an H-force set of G. In the paper the study of this parameter is introduced and its value or a lower bound for outerplanar graphs, planar graphs, k-connected graphs and prisms over graphs is determined.

On constant-weight TSP-tours

Scott Jones, P. Mark Kayll, Bojan Mohar, Walter D. Wallis (2003)

Discussiones Mathematicae Graph Theory

Similarity:

Is it possible to label the edges of Kₙ with distinct integer weights so that every Hamilton cycle has the same total weight? We give a local condition characterizing the labellings that witness this question's perhaps surprising affirmative answer. More generally, we address the question that arises when "Hamilton cycle" is replaced by "k-factor" for nonnegative integers k. Such edge-labellings are in correspondence with certain vertex-labellings, and the link allows us to determine...

Forbidden Pairs and (k,m)-Pancyclicity

Charles Brian Crane (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ {m, m+1, . . . , n}. This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree, Gould, Jacobson, and Lesniak in 2004. The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. We consider pairs of subgraphs that, when forbidden, guarantee hamiltonicity for 2-connected graphs...