Paired threshold graphs

DOI10.1016/J.DAM.2018.05.008zbMATH Open1398.05189arXiv1603.09701OpenAlexW2804069578WikidataQ129627816 ScholiaQ129627816MaRDI QIDQ1801073FDOQ1801073

Authors: Vida Ravanmehr, Gregory J. Puleo, Sadegh Bolouki, Olgica Milenkovic 

Publication date: 26 October 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1603.09701

Recommendations

• The threshold weight of a graph
• Statistical properties of a generalized threshold network model
• Random threshold graphs
• scientific article; zbMATH DE number 568830
• Cut-threshold graphs

zbMATH Keywords

threshold graphsunit interval graphsforbidden induced subgraphspolynomial-time graph recognition algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distance in graphs (05C12)

Cites Work

• Community structure in social and biological networks
• Collective dynamics of `small-world' networks
• Topics in Intersection Graph Theory
• Social and economic networks.
• Threshold graphs and related topics
• Incidence matrices and interval graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Simple linear time recognition of unit interval graphs
• The diameter of a scale-free random graph
• Foundational aspects of theories of measurement
• On the Complexity of Timetable and Multicommodity Flow Problems
• Triangulated graphs and the elimination process
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Quasi-threshold graphs
• Title not available (Why is that?)
• On the fractional intersection number of a graph
• Threshold graph limits and random threshold graphs
• Sur deux propriétés des classes d'ensembles
• Random threshold graphs
• The structure of geographical threshold graphs
• The Representation of a Graph by Set Intersections
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

Cited In (5)

• Threshold graphs
• Linear-time recognition of double-threshold graphs
• Mock threshold graphs
• Title not available (Why is that?)
• Tandem-win graphs

This page was built for publication: Paired threshold graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801073)