Two-\(\phi\)-tolerance competition graphs
type: Item
instance of: scholarly article
title: Two-\(\phi\)-tolerance competition graphs
zbMATH Open document ID: 0851.05085
DOI: 10.1016/0166-218X(96)80460-4
published in: Discrete Applied Mathematics
publication date: 1996-11-24T00:00:00Z
review text: A graph \(G= G(V, E)\) is a \(\phi\)-tolerance competition graph if there is a directed graph \(D= D(V, A)\) such that each vertex \(v_i\in V\) can be assigned a nonnegative integer \(t_i\) such that, for \(i\neq j\), \(v_i v_j\in E(G)\) iff \(|O(v_i)\cap O(v_j)|\geq \phi(t_i, t_j)\), where \(O(v)\) is the set of out-neighbors of \(v\) and where \(\phi\) is a symmetric function from \(\mathbb{N}\times \mathbb{N}\) into \(\mathbb{N}\). The not necessarily distinct integers \(t_i\) are called tolerances. In the present paper two-\(\phi\)-tolerance competition graphs are considered, these graphs are \(\phi\)-tolerance competition graphs in which the tolerances are selected from a set \(\{p, q\}\), and therefore such graphs are also designated as \(\{p, q\}\)-\(\phi\)-tolerance competition graphs. Further, the function \(\phi\) is restricted to the natural functions minimum (min), maximum (max), and sum. In Section 2 the case \(p= 0\) is treated and characterizations depending on an invariant which is called the \(q\)-edge clique cover number of \(G\) are given for \(\{0, q\}\)-min-tolerance competition graphs and for \(\{0, q\}\)-max-tolerance competition graphs (Theorems 1 and 3). For example, from Theorem 1 follows the special case (Theorem 2): Let \(G\) be a graph of order \(n\), let \(M\) be the set of its vertices of degree \(n- 1\), and suppose \(G- M\) has no isolated vertices. Then \(G\) is a \(\{0, q\}\)-min-tolerance competition graph iff \(G\) is a \(q\)-competition graph. By Theorem 4 a simple characterization of a \(\{0, 1\}\)-max-tolerance competition graph is given and from this follows that \(K_{2, 3}\) is such a graph (Corollary 2). Theorem 5 contains a characterization of a \(\{0, q\}\)-sum-tolerance competition graph. In Section 3 the tolerances are restricted to \(\{0, 1\}\). Let \(m\) be the class of \(\{0, 1\}\)-min-tolerance competition graphs and \(m'\) the class of graphs which are not \(\{0, 1\}\)-min-tolerance competition graphs. The classes …
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 897407
zbMATH Keywords: competition graph
zbMATH Keywords: tolerances
zbMATH Keywords: characterization
author: Robert Brigham
author: F. R. McMorris
author: Richard P. Vitray
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Tolerance competition graphs
cites work: A characterization of competition graphs
cites work: Competition graphs and clique dimensions
cites work: \((i,j)\) competition graphs
cites work: 2-Competition Graphs
cites work: A characterization of graphs of competition number m
cites work: A characterization of competition graphs of arbitrary digraphs
full work available at URL: 0166-218x(96)80460-4
OpenAlex ID: W2081367675
Recommended article: Q4863414
Recommended article: Fuzzy \(\phi\)-tolerance competition graphs
Recommended article: \(p\)-competition graphs
Recommended article: Q3822193
Recommended article: Q3689222
Recommended article: \((i,j)\) competition graphs
Recommended article: 2-Competition Graphs
Recommended article: Characterizations of competition multigraphs
Recommended article: Competition graphs and clique dimensions
Recommended article: Archimedean ϕ ‐tolerance graphs
description: scientific article; zbMATH DE number 897407