Premium
Multithreshold graphs
Author(s) -
Jamison Robert E.,
Sprague Alan P.
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22541
Subject(s) - combinatorics , mathematics , line graph , discrete mathematics , complement graph , block graph , graph , split graph , voltage graph , 1 planar graph
Multithreshold graphs are defined in terms of a finite sequence of real thresholds that break the real line into a set of regions, alternating between NO and YES. If real ranks can be assigned to the vertices of a graph in such a way that two vertices are adjacent iff the sum of their ranks lies in a YES region, then that graph is a multithreshold graph with respect to the given set of thresholds. If a graph can be represented with k or fewer thresholds, then it is k ‐threshold. The case of one threshold is the classical case introduced by Chvátal and Hammer. In this paper, we show for every graph G , there is a k such that G is k ‐threshold, and we exhibit graphs for which the required number of thresholds is linear in the order of the graph.