Title

Two-Φ-Tolerance Competition Graphs

Abstract

Let φ be a symmetric function defined from ℕ × ℕ into ℕ, where ℕ denotes the nonnegative integers. G = (V, E) is a φ-tolerance competition graph if there is a directed graph D = (V, A) and an assignment of a nonnegative integer ti to each vertex vi ∈ V such that, for i ≠ j, vivj ∈ E(G) if and only if |O(vi)∩O(vi)| ≥ φ(ti, tj), where O(x) = {y: xy ∈ A}. A two-φ-tolerance competition graph is a φ-tolerance competition graph in which all the ti are selected from a 2-set. Characterizations of such graphs, and relationships between them, are presented for φ equal to the minimum, maximum, and sum functions, with emphasis on the situation in which the 2-set is {0, q}.

Publication Date

4-30-1996

Publication Title

Discrete Applied Mathematics

Volume

66

Issue

2

Number of Pages

101-108

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/0166-218X(96)80460-4

Socpus ID

0346166148 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0346166148

This document is currently not available here.

Share

COinS