TY - JOUR

T1 - Paired threshold graphs

AU - Ravanmehr, Vida

AU - Puleo, Gregory J.

AU - Bolouki, Sadegh

AU - Milenković, Olgica

N1 - Funding Information:
The authors gratefully acknowledge funding from the NIH BD2K Targeted Software Program , under the contract number U01 CA198943-02 , and the NSF grants IOS1339388 , CCF 1117980 and NSF Center for Science of Information STC Class 2009 , under the award number 0939370 . The authors would also like to thank Hoang Dau, Pan Li and Hussein Tabatabei Yazdi at the University of Illinois for helpful discussions.
Funding Information:
The authors gratefully acknowledge funding from the NIH BD2K Targeted Software Program, under the contract number U01 CA198943-02, and the NSF grants IOS1339388, CCF 1117980 and NSF Center for Science of Information STC Class 2009, under the award number 0939370. The authors would also like to thank Hoang Dau, Pan Li and Hussein Tabatabei Yazdi at the University of Illinois for helpful discussions.

PY - 2018/12/11

Y1 - 2018/12/11

N2 - Threshold graphs are recursive deterministic network models that have been proposed for describing certain economic and social interactions. One drawback of this graph family is that it has limited generative attachment rules. To mitigate this problem, we introduce a new class of graphs termed Paired Threshold (PT) graphs described through vertex weights that govern the existence of edges via two inequalities. One inequality imposes the constraint that the sum of weights of adjacent vertices has to exceed a specified threshold. The second inequality ensures that adjacent vertices have a weight difference upper bounded by another threshold. We provide a conceptually simple characterization and decomposition of PT graphs, analyze their forbidden induced subgraphs and present a method for performing vertex weight assignments on PT graphs that satisfy the defining constraints. Furthermore, we describe a polynomial-time algorithm for recognizing PT graphs. We conclude our exposition with an analysis of the intersection number, diameter and clustering coefficient of PT graphs.

AB - Threshold graphs are recursive deterministic network models that have been proposed for describing certain economic and social interactions. One drawback of this graph family is that it has limited generative attachment rules. To mitigate this problem, we introduce a new class of graphs termed Paired Threshold (PT) graphs described through vertex weights that govern the existence of edges via two inequalities. One inequality imposes the constraint that the sum of weights of adjacent vertices has to exceed a specified threshold. The second inequality ensures that adjacent vertices have a weight difference upper bounded by another threshold. We provide a conceptually simple characterization and decomposition of PT graphs, analyze their forbidden induced subgraphs and present a method for performing vertex weight assignments on PT graphs that satisfy the defining constraints. Furthermore, we describe a polynomial-time algorithm for recognizing PT graphs. We conclude our exposition with an analysis of the intersection number, diameter and clustering coefficient of PT graphs.

KW - Forbidden induced subgraphs

KW - Polynomial-time graph recognition algorithms

KW - Threshold graphs

KW - Unit interval graphs

UR - http://www.scopus.com/inward/record.url?scp=85048301482&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85048301482&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2018.05.008

DO - 10.1016/j.dam.2018.05.008

M3 - Article

AN - SCOPUS:85048301482

VL - 250

SP - 291

EP - 308

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -