Premium
Archimedean ϕ ‐tolerance graphs
Author(s) -
Golumbic Martin Charles,
Jamison Robert E.,
Trenk Ann N.
Publication year - 2002
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.10060
Subject(s) - combinatorics , mathematics , discrete mathematics , bipartite graph , graph , distance hereditary graph , line graph , symmetric graph , voltage graph
Let ϕ be a symmetric binary function, positive valued on positive arguments. A graph G = ( V , E ) is a ϕ‐ tolerance graph if each vertex υ ∈ V can be assigned a closed interval I υ and a positive tolerance t υ so that xy ∈ E ⇔ | I x ∩ I y |≥ ϕ ( t x , t y ). An Archimedean function has the property of tending to infinity whenever one of its arguments tends to infinity. Generalizing a known result of [15] for trees, we prove that every graph in a large class (which includes all chordless suns and cacti and the complete bipartite graphs K 2, k ) is a ϕ‐tolerance graph for all Archimedean functions ϕ. This property does not hold for most graphs. Next, we present the result that every graph G can be represented as a ϕ G ‐tolerance graph for some Archimedean polynomial ϕ G . Finally, we prove that there is a „universal” Archimedean function ϕ * such that every graph G is a ϕ * ‐tolerance graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 179–194, 2002