Collapsible graphs and reductions of line graphs

Zhi Hong Chen*, Peter C.B. Lam, Wai Chee SHIU

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)


A graph G is collapsible if for every even subset X ⊆ V (G), G has a subgraph Γ such that G - E (Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364].

Original languageEnglish
Pages (from-to)3173-3184
Number of pages12
JournalDiscrete Mathematics
Issue number10
Publication statusPublished - 28 May 2009

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Collapsible graph
  • Double cycle covers
  • Hamiltonian index
  • Line graphs
  • Reduction of graph


Dive into the research topics of 'Collapsible graphs and reductions of line graphs'. Together they form a unique fingerprint.

Cite this