Recognizing hinge-free line graphs and total graphs

Jou Ming Chang, Chin Wen Ho

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

In this paper, we characterize line graphs and total graphs that are hinge-free, i.e., there is no triple of vertices x,y,z such that the distance between y and z increases after x is removed. Based on our characterizations, we show that given a graph G with n vertices and m edges, determining its line graph and total graph to be hinge-free can be solved in O(n + m) time. Moreover, characterizations of hinge-free iterated line graphs and total graphs are also discussed.

Original languageEnglish
Pages (from-to)789-801
Number of pages13
JournalTaiwanese Journal of Mathematics
Volume5
Issue number4
DOIs
StatePublished - Dec 2001

Keywords

  • Cograph
  • Hinge-free graph
  • Line graph
  • Total graph

Fingerprint

Dive into the research topics of 'Recognizing hinge-free line graphs and total graphs'. Together they form a unique fingerprint.

Cite this