Currently displaying 1 – 5 of 5

Showing per page

Order by Relevance | Title | Year of publication

The Ryjáček Closure and a Forbidden Subgraph

Akira SaitoLiming Xiong — 2016

Discussiones Mathematicae Graph Theory

The Ryjáček closure is a powerful tool in the study of Hamiltonian properties of claw-free graphs. Because of its usefulness, we may hope to use it in the classes of graphs defined by another forbidden subgraph. In this note, we give a negative answer to this hope, and show that the claw is the only forbidden subgraph that produces non-trivial results on Hamiltonicity by the use of the Ryjáček closure.

2-factors in claw-free graphs with locally disconnected vertices

Mingqiang AnLiming XiongRunli Tian — 2015

Czechoslovak Mathematical Journal

An edge of G is singular if it does not lie on any triangle of G ; otherwise, it is non-singular. A vertex u of a graph G is called locally connected if the induced subgraph G [ N ( u ) ] by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph G of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex v of degree at least 3 in G , there is a nonnegative integer s such that v lies...

Degree sums of adjacent vertices for traceability of claw-free graphs

Tao TianLiming XiongZhi-Hong ChenShipeng Wang — 2022

Czechoslovak Mathematical Journal

The line graph of a graph G , denoted by L ( G ) , has E ( G ) as its vertex set, where two vertices in L ( G ) are adjacent if and only if the corresponding edges in G have a vertex in common. For a graph H , define σ ¯ 2 ( H ) = min { d ( u ) + d ( v ) : u v E ( H ) } . Let H be a 2-connected claw-free simple graph of order n with δ ( H ) 3 . We show that, if σ ¯ 2 ( H ) 1 7 ( 2 n - 5 ) and n is sufficiently large, then either H is traceable or the Ryjáček’s closure cl ( H ) = L ( G ) , where G is an essentially 2 -edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10 which have...

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)