Characterization and Linear-Time Recognition of Paired Threshold Graphs

Yixin Cao, Guozhen Rong, Jianxin Wang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

In a paired threshold graph, each vertex has a weight, and two vertices are adjacent if and only if their weight sum is large enough and their weight difference is small enough. It generalizes threshold graphs and unit interval graphs, both very well studied. We present a vertex ordering characterization of this graph class, which enables us to prove that it is a subclass of interval graphs. Further study of clique paths of paired threshold graphs leads to a simple linear-time recognition algorithm for the graph class.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Revised Selected Papers
EditorsIsolde Adler, Haiko Müller
PublisherSpringer Science and Business Media Deutschland GmbH
Pages298-309
Number of pages12
ISBN (Print)9783030604394
DOIs
Publication statusPublished - 2020
Event46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2020 - Leeds, United Kingdom
Duration: 24 Jun 202026 Jun 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12301 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2020
Country/TerritoryUnited Kingdom
CityLeeds
Period24/06/2026/06/20

Keywords

  • (Paired) threshold graph
  • (Unit) interval graph
  • Broom ordering
  • Clique path
  • Interval model
  • Interval ordering
  • Umbrella ordering

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this