z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here