Note on two-φ-tolerance competition graphs
Journal
Proceedings - 2010 1st ACIS International Symposium on Cryptography, and Network Security, Data Mining and Knowledge Discovery, E-Commerce and Its Applications, and Embedded Systems, CDEE 2010
Pages
59-62
Date Issued
2011
Author(s)
Abstract
Let φ be a symmetric function defined from N×N into N, where N denotes the nonnegative integers. A graph G=(V,E) is a φ-tolerance competition graph if there is a digraph D=(V,A) such that each vertex v i ∈V can be assigned a nonnegative integer t i such that, for i≠j, v i v j ∈E if and only if |O(v i )∩O(v j )|≥φ(t i ,t j ). Brigham et al. defined the two-φ-tolerance competition graph as a tolerance competition graph in which all the t i are selected from a 2-set. They characterized such graphs and discussed the relationships between them for φ equal to the minimum, maximum, and sum functions, with emphasis on the situation in which the 2-set is {0,q}. In this paper, we continue to study two-φ-tolerance competition graphs. Characterizations of such graphs, and the lower bounds of θ φ {p,q} (G), are presented for φ=min, max and sum, respectively, with emphasis on the situation in which the 2-set is {p,q}.
Type
conference paper