Paired threshold graphs

DOI10.1016/J.DAM.2018.05.008MaRDI QIDQ1801073zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• scientific article; zbMATH DE number 2229025 (Why is no real title available?)
• Addendum: 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
• Collective dynamics of `small-world' networks
• Community structure in social and biological networks
• Foundational aspects of theories of measurement
• Incidence matrices and interval graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the fractional intersection number of a graph
• Quasi-threshold graphs
• Random threshold graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Simple linear time recognition of unit interval graphs
• Social and economic networks.
• Sur deux propriétés des classes d'ensembles
• The Representation of a Graph by Set Intersections
• The diameter of a scale-free random graph
• The structure of geographical threshold graphs
• Threshold graph limits and random threshold graphs
• Threshold graphs and related topics
• Topics in Intersection Graph Theory
• Triangulated graphs and the elimination process

Cited in

(5)

• Mock threshold graphs
• scientific article; zbMATH DE number 7378386 (Why is no real title available?)
• Linear-time recognition of double-threshold graphs
• Threshold graphs
• 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)