Traceability on 2-connected line graphs

Tao Tian, Liming Xiong*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

In this paper, we mainly prove the following: Let G be a connected almost bridgeless simple graph of order n sufficiently large such that σ¯2(G)=min{d(u)+d(v):uv∈E(G)}≥2(⌊n/11⌋−1). Then either L(G) is traceable or Catlin's reduction of the core of G is one of eight graphs of order 10 or 11, where the core of G is obtained from G by deleting the vertices of degree 1 of G and replacing each path of length 2 whose internal vertex has degree 2 in G by an edge. We also give a new proof for the similar theorem in Niu et al. (2012) which has flaws in their proof.

Original languageEnglish
Pages (from-to)463-471
Number of pages9
JournalApplied Mathematics and Computation
Volume321
DOIs
Publication statusPublished - 15 Mar 2018

Keywords

  • Dominating trail
  • Line graph
  • Spanning trail
  • Traceable

Fingerprint

Dive into the research topics of 'Traceability on 2-connected line graphs'. Together they form a unique fingerprint.

Cite this