Wyniki wyszukiwania

1

Heavy Subgraph Conditions for Longest Cycles to Be Heavy in Graphs

100%

Lia B., Zhang S.

Discussiones Mathematicae Graph Theory

|

2016

|

tom 36

|

nr 2

383-392

EN

Let G be a graph on n vertices. A vertex of G with degree at least n/2 is called a heavy vertex, and a cycle of G which contains all the heavy vertices of G is called a heavy cycle. In this note, we characterize graphs which contain no heavy cycles. For a given graph H, we say that G is H-heavy if every induced subgraph of G isomorphic to H contains two nonadjacent vertices with degree sum at least n. We find all the connected graphs S such that a 2-connected graph G being S-heavy implies any longest cycle of G is a heavy cycle.

2

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

A σ₃ type condition for heavy cycles in weighted graphs

81%

Zhang S., Li X., Broersma H.

Discussiones Mathematicae Graph Theory

|

2001

|

tom 21

|

nr 2

159-166

EN

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) for every vertex z ∈ N(x)∩N(y) with d(x,y) = 2; 3. In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains either a Hamilton cycle or a cycle of weight at least 2m/3. This generalizes a theorem of Fournier and Fraisse on the existence of long cycles in k-connected unweighted graphs in the case k = 2. Our proof of the above result also suggests a new proof to the theorem of Fournier and Fraisse in the case k = 2.

3

Heavy subgraph pairs for traceability of block-chains

81%

Li B., Broersma H., Zhang S.

Discussiones Mathematicae Graph Theory

|

2014

|

tom 34

|

nr 2

287-307

EN

A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o−1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least n−1 in G. A block-chain is a graph whose block graph is a path, i.e., it is either a P1, P2, or a 2-connected graph, or a graph with at least one cut vertex and exactly two end-blocks. Obviously, every traceable graph is a block-chain, but the reverse does not hold. In this paper we characterize all the pairs of connected o−1-heavy graphs that guarantee traceability of block-chains. Our main result is a common extension of earlier work on degree sum conditions, forbidden subgraph conditions and heavy subgraph conditions for traceability

4

Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs

81%

Li B., Broersma H. J., Zhang S.

Discussiones Mathematicae Graph Theory

|

2016

|

tom 36

|

nr 4

915-929

EN

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.

Ograniczanie wyników

4 Discussiones Mathematicae Graph Theory

4 Zhang S.

2 Broersma H.

2 Li B.

1 Broersma H. J.

1 Li X.

1 Lia B.

2 2016

1 2014

1 2001

Heavy Subgraph Conditions for Longest Cycles to Be Heavy in Graphs

A σ₃ type condition for heavy cycles in weighted graphs

Heavy subgraph pairs for traceability of block-chains

Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs