Currently displaying 1 – 8 of 8

Showing per page

Order by Relevance | Title | Year of publication

An Implicit Weighted Degree Condition For Heavy Cycles

Junqing CaiHao LiWantao Ning — 2014

Discussiones Mathematicae Graph Theory

For a vertex v in a weighted graph G, idw(v) denotes the implicit weighted degree of v. In this paper, we obtain the following result: Let G be a 2-connected weighted graph which satisfies the following conditions: (a) The implicit weighted degree sum of any three independent vertices is at least t; (b) w(xz) = w(yz) for every vertex z ∈ N(x) ∩ N(y) with xy /∈ E(G); (c) 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...

Pancyclism and small cycles in graphs

Ralph FaudreeOdile FavaronEvelyne FlandrinHao Li — 1996

Discussiones Mathematicae Graph Theory

We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (dC(u,v)+1, [(n+19)/13]), d C ( u , v ) being the distance of u and v on a hamiltonian cycle of G.

Chvátal-Erdos condition and pancyclism

Evelyne FlandrinHao LiAntoni MarczykIngo SchiermeyerMariusz Woźniak — 2006

Discussiones Mathematicae Graph Theory

The well-known Chvátal-Erdős theorem states that if the stability number α of a graph G is not greater than its connectivity then G is hamiltonian. In 1974 Erdős showed that if, additionally, the order of the graph is sufficiently large with respect to α, then G is pancyclic. His proof is based on the properties of cycle-complete graph Ramsey numbers. In this paper we show that a similar result can be easily proved by applying only classical Ramsey numbers.

A Note on Neighbor Expanded Sum Distinguishing Index

Evelyne FlandrinHao LiAntoni MarczykJean-François SacléMariusz Woźniak — 2017

Discussiones Mathematicae Graph Theory

A total k-coloring of a graph G is a coloring of vertices and edges of G using colors of the set [k] = {1, . . . , k}. These colors can be used to distinguish the vertices of G. There are many possibilities of such a distinction. In this paper, we consider the sum of colors on incident edges and adjacent vertices.

Two operations on a graph preserving the (non)existence of 2-factors in its line graph

Mingqiang AnHong-Jian LaiHao LiGuifu SuRunli TianLiming Xiong — 2014

Czechoslovak Mathematical Journal

Let G = ( V ( G ) , E ( G ) ) be a graph. Gould and Hynds (1999) showed a well-known characterization of G by its line graph L ( G ) that has a 2-factor. In this paper, by defining two operations, we present a characterization for a graph G to have a 2-factor in its line graph L ( G ) . A graph G is called N 2 -locally connected if for every vertex x V ( G ) , G [ { y V ( G ) 1 dist G ( x , y ) 2 } ] is connected. By applying the new characterization, we prove that every claw-free graph in which every edge lies on a cycle of length at most five and in which every vertex...

Page 1

Download Results (CSV)