Archimedean ϕ -tolerance graphs

✍ Scribed by Martin Charles Golumbic; Robert E. Jamison; Ann N. Trenk

• Publisher: John Wiley and Sons
• Year: 2002
• Tongue: English
• Weight: 143 KB
• Volume: 41
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.10060

✦ Synopsis

Abstract

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